我在最近的比赛中遇到了一个问题.我无法找到解决方案,也没有关于这个问题的社论.
我在这里也引用了问题陈述,以防链接不起作用.
求出整数n大于或等于A且小于或等于B(A <= n <= B),并且2 ^ n的十进制表示以n结尾.
例如: 2 ^ 36 = 68719476736,以"36"结尾.
INPUT
第一行包含整数T,即测试用例的数量.随后是T行,每行包含两个整数A和B.
约束
1 <= T <= 10^5
A<=B
A,B <= 10^150
OUTPUT
打印T行,每行包含相应测试用例的答案.
样本输入
2
36 36
100 500
样本输出
1
0
正如在编程竞赛中经常发生的那样,我提出了一个我没有证明过的启发式方法,但看起来似乎有道理.我写了一个简短的程序,找到最多1000000的数字,它们是:
36
736
8736
48736
948736
因此,我的理论如下 - 每个连续数字后缀为前一个,只增加一个数字.希望这会让你找到解决问题的正确方法.请注意,如果我的假设是正确的,您只需要找到150个数字并找到每个连续的数字,则需要检查可能添加的9个数字.
对类似问题的一般建议 - 总是试图找到前几个数字并考虑一些关系.
同样经常发生在竞争中,你提出的理论就像我上面提出的理论,但没有时间去证明它.你没有时间证明它.只希望你是对的和代码.
编辑:我相信我能够证明我的猜想(实际上我错过了一些数字 - 见帖子的结尾).首先让我指出,正如v3ga在评论中指出的那样,上面的算法可以解决,直到75353432948736没有数字可以根据你给出的定义使新数字"有趣".但是我完全错过了另一个选项 - 你可以在前面添加一些0,然后添加一个非零数字.
我现在将证明一个引理:
引理:如果1 a 2 ... a n是一个有趣的数字且n大于3,那么2 ... a n也很有趣.
证明:2 a 1 a 2 ... a n = 2 a 1*10 n - 1*2 a 2 a 2 ... a n
现在我将证明2 a 1*10 n - 1*2 a 2 a 2 ... a n与2 a 2 a 2 ... a n modulo 10 n-1相当.
要做到这一点,我们可以证明2 a 1*10 n - 1*2 a 2 a 2 ... a n - 2 a 2 a 2 ... a n可以被10 n-1整除.
2 a 1*10 n - 1*2 a 2 a 2 ... a n - 2 a 2 a 2 ... a n = 2 a 2 a 2 ... a n*(2 a 1*10 n - 1 - 1)a 2 a 2 ... a n对于我们考虑的值大于n-1.
因此,所有留下来证明有10 n-1除以差值的是5 n-1除以2 a 1*10 n - 1 - 1.
为此,我将使用欧拉定理:
2 phi(5 n-1) = 1(模5 n-1).
现在phi(5 n-1)= 4*(5 n-2)并且对于n> = 3 4*(5 n-2)将划分1*10 n-1(实际上甚至仅10 n-1).
因此,2 a 1*10 n-1给出余数1模5 n-1,因此5 n-1除以2 a 1*10 n-1 -1.
因此,10 n-1除以2 a 2 a 2 ... a n*(2 a 1*10 n - 1 - 1),因此最后n - 1位为2 a 1 a 2 a 2 ... a n和2a a 2 a 3 a 4 ... a n是相同的.
现在作为1 a 2 a 2 ... a n很有趣,最后n个数字是2 a 1 a 2 a 2 ... a n是1 a 2 a 2 ... a n,所以最后的n-的2 1位一2一3一4 ...一个ñ是一个2一个3一个4 ...一个ñ并且因此一2一3一4 ...一个ñ也是有趣.QED.
使用此引理,您将能够解决问题.请注意,您也可以添加一些零,然后添加一个非零数字.