远端评测题 1000ms 256MiB

GCD Sum

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

GCD Sum

题目描述

gcdSum(x)=gcd(x,i=1kai)\operatorname{gcdSum(x)=}\gcd(x,\sum_{i=1}^ka_i)

其中 aia_i 表示 xx 的从左到右第 ii 位,kk 表示 xx 的位数。

例如 $\operatorname{gcdSum(762)}=\gcd(762,2+6+7)=\gcd(762,15)=3$

给定一个 nn,请你找到一个最小的整数 xx 满足:

  • xnx\ge n
  • gcdSum(x)>1\operatorname{gcdSum(x)}>1

输入格式

输入的第一行为一个整数tt1t104(1\le t\le 10^4)——测试用例的数量。 接下来是tt行,每行包含一个整数n n (1n1018) (1 \le n \le 10^{18}) 。 一个测试中的所有测试用例都是不同的。

输出格式

输出tt行,其中第ii行是一个包含第iith测试用例答案的单个整数。

样例 #1

样例输入 #1

3
11
31
75

样例输出 #1

12
33
75

提示

让我们解释一下样本中的三个测试用例。 测试用例1:n=11n=11\text{gcdSum}(11=gcd111+1=gcd112=1}(11)= gcd(11,1+1)= gcd(11,2)= 1\text{gcdSum}(12=gcd121+2=gcd123=3}(12)=gcd(12,1+2)=gcd(12,3)=3。 因此,gcdSumgcdSum>1>1的最小数字11\ge111212。 测试用例2:n=31n=31\text{gcdSum}(31=gcd313+1=gcd314=1}(31)=gcd(31,3+1)=gcd(31,4)=1\text{gcdSum}(32=gcd323+2=gcd325=1}(32)=gcd(32,3+2)=gcd(32,5)=1\text{gcdSum}(33=gcd333+3=gcd336=3}(33)=gcd(33,3+3)=gcd(33,6)=3。 因此,gcdSumgcdSum>1>1的最小数字31\ge313333。 测试用例3:n=75n=75\text{gcdSum}(75=gcd757+5=gcd7512=3}(75)=gcd(75,7+5)=gcd(75,12)=37575\text{gcdSum已经是>1>1。因此,这就是答案。

11.26上午8点半练习及作业

未认领
状态
已结束
题目
13
开始时间
2023-11-25 0:00
截止时间
2023-12-8 23:59
可延期
24 小时