鸣谢：
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"
