[POJ3696]The Luckiest number(数论)

题目: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,所以肯定不存在样的解

然后就解决了……

上一篇:Swift3.0 函数闭包与OC Block


下一篇:<转> linux进程状态的说明