poj 3696
题意：
给出一个数字L,求出最短的888...8能被L整除，输出最短的长度。
限制：
1 <= L <= 2*10^9
思路：
设x为最小长度
888...8=(10^x-1)/9*8
由题意得：
(10^x-1)/9*8 % L=0
-> (10^x-1)*8 % (9L) = 0
-> (10^x-1) % (9L/gcd(L,8)) = 0
-> 10^x % (9L/gcd(L,8)) = 1
这个是一个离散对数的问题，第一个想到的是用拓展BSGS做，但超时了。
因为余数为1
可以想到欧拉定理：a^phi(m) % m = 1 , 在a与m互质的条件下。
回到这道题：
在10 与 9L/gcd(L,8) 不互质的条件下，无解
在10 与 9L/gcd(L,8) 互质的条件下
求出tmp=phi(9L/gcd(L,8))，然后O(sqrt(tmp))枚举tmp的因子，选出最小的符合条件的因子就行了。
poj 3696 欧拉函数
原文：http://blog.csdn.net/whai362/article/details/43908013
