XTUOJ-1223 Repeat One

题目描述

求由最小的一个N,N个数码1组成的数能被M整除? 比如M=3时,111能被3整除。M=2时,则不存在这样的N。

输入

第一行是一个整数K(K≤1,000),表示样例的个数。 以后每行一个整数M(1≤M≤1,000,000)

输出

每行输出一个样例的结果,如果不存在这样的N,输出0。

样例输入

5
1
2
3
4
999989

样例输出

1
0
3
0
473670

思路

题目十分良心地给出了 M = 999989 时的答案,告诉我们哪怕时限有三秒,我们也无法通过高精度直接暴力,但我没试过高精行不行

然后先思考 M 的取值,显然 N 个数码 1 组成的数是奇数,所以 M 也要是奇数。

并且当 M 为 5 的倍数时,末尾得是 0 或 5,不符合我们的 1 ,所以也不行。

剩下的就是优美的暴力了。

我们可以大胆的猜测(我现在不会证明,从样例目测出来,估计数论知识,希望大佬能告诉我为什么),最大的位数有 M 位,超出就是不存在。

然后从循环 M 次,每次增加一位数,当数 n 能被 M 整除时跳出。

先让数 n 初始化为 1,然后利用取模的性质,将它化简为 n %= M,避免爆精度。

取模的性质(百度来的):

(a + b) % p = (a % p + b % p) % p
(a * b) % p = (a % p * b % p) % p
((a*b) % p * c) % p = (a * (b*c) % p) % p 
1111 % M = (111*10 + 1) % M = ((111*10)%M + 1%M) % M = (111%M*10 + 1) % M = ((11*10 + 1) % M) * 10 + 1) % M = (11%M*10 + 1) % M) * 10 + 1) % M = ((((1%M*10 + 1) % M) * 10 + 1)* 10 + 1) % M

看到 1111%M,111%M,11%M,1%M 了吧,这样就能保存上次的结果了。

当循环结束之后,如果数 n 为 0,那就输出循环次数。

为了 Top 20 Runs,没用 for 循环,但现在发现忘记打 register 了。。。

文章目录