给定一个数,判断是否存在一个全由8组成的数为这个数的倍数 若存在则输出这个数的长度,否则输出0 写了好久实在想不出来,对着别人的题解才把题目做出来... 通过这个题学会了快速幂,但是代码中说的乘法转化还是看不懂... 百度了一下才知道这个题目是区预赛的题,看来自己和别人还有很多差距啊 ------------------------------------------------------------------------------------------------------------------------------ 原文:http://blog.csdn.net/ok_again/article/details/17077195  首先，由题意可以得出，(10^x - 1)/ 9 * 8 = L * p(p是一个未知数，但必定是整数)。            然后对上式进行移项处理，得：(10^x - 1) = 9 * L * p / 8。            设m = 9 * L / gcd(L, 8)，则有(10^x - 1) = m * p'。p’是必然存在的一个整数。            然后问题就转化成为了 10^x = 1(mod m)，观察此式，显然，m和10必定互质。            于是根据欧拉定理，10^(Euler(m)) = 1(mod m) 。由于题目要求最小的解，解必然是Euler(m)的因子。            需要注意的是，对于10^x，由于m太大，直接快速幂相乘的时候会超long long。。。。好bug，需要乘法转化一下。 代码如下: #include #include #include #include #define LL long long #define MAXN 400010 using namespace std; bool vis[MAXN]; vector hav; vector prime; LL gcd(LL a, LL b) { return b==0 ? a : gcd(b, a%b); } void gen_primes() { for(int i=2; i 1) { ans = ans/n*(n-1); } return ans; } LL Mul(LL a, LL b, LL c) { LL ans = 0; while(b) { if(b & 1) ans = (ans+a)%c; a = a*2%c; b >>= 1; } return ans; } LL Pow(LL a, LL b, LL c) { LL ans = 1; while(b) { if(b & 1) ans = Mul(ans, a, c); a = Mul(a, a, c); b >>= 1; } return ans; } void get_hav(LL n) { hav.clear(); for(int i=0; i1; ++i) { while(n%(LL)prime[i] == 0) { n /= prime[i]; hav.push_back(prime[i]); } } if(n > 1) hav.push_back(n); } int main(void) { LL n, m, x, cas = 1; gen_primes(); while(cin >> n && n) { m = 9*n/gcd(n, 8LL); if(gcd(m, 10LL) != 1) { cout << "Case " << cas++ << ": 0" << endl; continue; } x = euler_phi(m); get_hav(x); for(int i=0; i