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