鸣谢： 
http://blog.csdn.net/yhrun/article/details/6908470 
http://blog.sina.com.cn/s/blog_6a46cc3f0100tvqg.html

题意：链接君已失效

方法：各种数论

解析：老师找了两道数论题。这是第一道，听说比第二道简单多了。然而我并不会，看题解也是好顿理解，这题太值得做了！不做悔一生。

咳，回归正题。这道题就是一个奇妙的数。问你最短须要多少个8组成的数能整除他？所以你有思路么？并没有！有思路你也不会来看我唠叨了！

所以接下来，请你清理下脑子，来看我论证。

首先呢我们能够这么理解

8∗(10x−1)/9=k∗L当中k为常数

然后呢由于这个9在分母上。如果涉及取余或者什么东西的话会非常麻烦。所以我们把它乘到右边，然后会变成什么呢？

8∗(10x−1)=9∗k∗L（我知道以上都是废话）

再进一步8∗(10x−1)/gcd(8,L)=9∗k∗L/gcd(8,L)

接下来便于计算

我们令p=8/gcd(8,L),q=9∗L/gcd(8,L)

所以原式变为(10x−1)∗p=k∗q

由于p与q是互质的，这就是为什么我除了个最大公约数。

所以(10x−1)

即10x≡1(modq)

又依据欧拉定理

gcd(a,b)==1可得到aφ(b)≡1(modb)

所以10φ(q)≡1(modq)

之后呢又有这么个结论，最小的解为φ(q)的因子。这个呢是原根的某个定理的推论，简单说明一下原因呢是这种

设k不是φ(n)的约数

10k≡1(modn)

如果gcd(k,φ(n))=s，必定有一个数a，a是k的倍数。a+s是φ(n)的倍数。

10a≡10k≡1(modn)

10(a+s)≡10φ(n)≡1(modn)

所以10s≡1(modn)

而k不是φ(n)的约数，s是φ(n)的约数，s又是k的约数

所以s＜k。而若k是符合要求的，则必定有一个更小的s。

所以答案一定是φ(n)的约数。

之后就乱搞吧！

友情提示！

欧拉可能算爆long long

所以***把9单独讨论。

代码：

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#define N 1001002*Nintintqforint2100000ifforint1*i100000*i1if%prime0break0whileif1%q%q1return1whileif11returnwhile%breturnforint1*primeif%prime0*(1while%prime0if1*(1returnintint0while"%lld"00printf"Case %d: "q8if109*q1printf"0\n"continueelseqifq%30*=6else*=9q*=9for1*iif%i0sort11int0forint1if101printf"%lld\n"1breakifprintf"0\n"