XTUOJ-1223 Repeat One 作者: ASC_8384 时间: 2019-08-26 分类: 学习,题解,算法与数据结构 本文最后更新于2019年08月26日，已超过154天没有更新。 请自行判断文章内容，如有问题请留言反馈，说不定会处理，手动滑稽 # 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 了。。。~~ 标签: 算法, 题解