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 了。。。