原题面：https://vjudge.net/problem/POJ-3696
题目大意：给定一个正整数L（1<=L<=2e9），问至少多少个8连在一起组成的正整数是L的倍数？
输入描述：多组输入，每次输入一个L，直到L为0结束输入。
输出描述：对于每组数据，输出至少多少个8连在一起可以组成L的倍数。
样例输入：
8 11 16 0
样例输出：
Case 1: 1 Case 2: 2 Case 3: 0
分析：x个8组成的正整数可以写作8(pow(10,x)-1)/9。题目就是想让我们求出一个最小的满足情况的x。L|8（pow(10,x)-1）/9<-->9L|8(pow(10,x)-1)<-->9L/d|pow(10,x)-1<-->pow(10,x)==1(mod9L/d)。若正整数a,n互质，则满足pow(a,x)==1(mod n)的最小正整数x0是phi(n)的约数。注意该死的慢速乘，题目给的数据范围中间爆了long long,真是有毒，wa死我了，几天了才A。
代码：
#include<iostream> #include<cstdio> #include<algorithm> using namespace std; typedef long long ll; ll divisor[10000007]; int cnt; ll gcd(ll a,ll b) { return !b ? a : gcd(b, a % b); } ll phi(ll n) { ll ans = n; for (ll i = 2; i * i <= n; i++) { if (n % i == 0) { ans = ans - ans / i; while (n % i == 0) n /= i; } } if (n > 1) ans = ans - ans / n; return ans; } void depart(ll n) { cnt = 0; for (ll i = 1; i * i <= n; i++) { if (n % i == 0) { divisor[cnt++] = i; if (n != i * i) { divisor[cnt++] = n / i; } } } } ll mul(ll a,ll b,ll m){ ll res=0; while(b){ if(b&1) res=(res+a)%m; a=(a+a)%m; b>>=1; } return res; } ll spow(ll a,ll b,ll m) { ll res = 1; a %= m; while (b) { if (b & 1) res = mul(res, a, m); a = mul(a, a, m); b >>= 1; } return res; } int main() { ll L, d, ans; int kase = 0; while (cin>>L) { if(L==0) break; d = gcd(L, 8LL); ans = 0; ll m = 9 * L / d; if (gcd(10, m) != 1) { printf("Case %d: %lld ", ++kase, ans); continue; } depart(phi(m)); sort(divisor, divisor + cnt); //unique(divisor.begin(),divisor.end()); for (int i = 0; i < cnt; i++) { if (spow(10, divisor[i], m) == 1) { ans = divisor[i]; break; } } printf("Case %d: %lld ", ++kase, ans);// "Case " << ++kase << ": " << ans << endl; } return 0; }