题目:http://poj.org/problem?id=3696
题意:给你一个数字L,你要求出一个数N,使得N是L的倍数,且N的每位数都必须是8,输出N的位数(如果不存在输出0)
分析:
首先我们假设N是x个8组成的
那么88888...888=kL
提个8出来:8*111..1111=kL ①
因为题目只要求x的值,所以要弄出关于x的方程
11...111可以写成(10^k-1)/9
于是①变成了8(10^x-1)=9kL ②
再来回顾下题目,②式中x和k是变量,且都属于正整数,要根据②式求出最小的x
这不是一般的二元一次不定方程,这里的x在指数上
编程里面能解未知数在指数上面的这类方程的东西只有什么???是的只有这个式子:10^x=1(mod q)
于是想办法把②往这种形式上靠
可以这样变形8(10^x-1)/gcd(L,8)=9kL/gcd(L,8)
设p=8/gcd(L,8),q=L/gcd(L,8)
则p(10^x-1)=kq且p,q互质
那么肯定有10^x-1=0(mod q)
即10^x=1(mod q) ③
很明显如果gcd(10,q)=1,那么肯定可以,比如果x=φ(q),当然,要求最小,就枚举φ(q)因数
如果gcd(10,q)=d(d不是1),那么有10^x % d=0,不妨设md=10^x,设q=nd则10^x%q=md % nd=md-y(nd)=d(m-yn)一定是d的倍数,而不是1,所以肯定不存在样的解
然后就解决了……