POJ The Luckiest number 3696 数论（处理快速幂过程中超int64的情况）
此题大意就是给出一个数x 问他是否能乘以某个数后变成另一个数，使得每位都是8，然后问这个数的长度
我们观察888....这种数，可以发现，一个数如果能乘以某个数变成他，因子中不能有5，并且最多有3个2.
那么我们就先把所有的2因子都去掉，下面就是看他是否能乘某个数变成111....这样的数了
而111.... =( 10^m - 1) / 9
并且111...要mod x =0
那么就是( 10^m - 1) / 9 % x = 0
因为( 10^m - 1)必然可以整除掉9。所以不妨将上面的式子转化一下
( 10^m - 1) %(9 * x)= 0
即10^m % (9 * x) = 1
好了 ，由于我们刚才已经干掉了2因子和5因子，所以10^m显然和(9 * x)是互质的
那么可以发现这和欧拉函数怎么这么像。
没错，如果令m = phi(9 * x) 这个式子一定成立
但是我们要求最小的m啊
那么就去找phi(x)的因子了，找其中最小的因子k使得10^k % (9 * x) = 1 因为1乘1还是1么，所以这么干是很合理的
还有一个需要注意的是
快速幂取模的时候很蛋疼 ，因为有某些数是超int的，也就导致两数相乘超了int64
这就需要把乘法特殊处理一下，类似于那种快速幂的做法
#include <iostream>#include <algorithm>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <queue>#include <map>#include <set>#define MAXN 111111#define MAXM 555555#define INF 1000000011#define lch(x) x<<1#define rch(x) x<<1|1#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1#define eps 1e-7using namespace std;long long euler(long long n){ long long x = n; long long i; long long phi = n; for (i = 2LL; i * i <= x; i++) { if (x % i == 0) { phi = phi / i * (i - 1LL) ; while (x % i == 0) x /= i; } } if (x != 1LL) phi = phi / x * (x - 1LL); return phi;}long long multi(long long a, long long b, long long c){ long long ret=0; while(b) { if(b&1) { ret+=a; if(ret>=c) ret-=c; } a+=a; if(a>=c) a-=c; b>>=1; } return ret;}long long fastmod(long long a, long long b, long long c)//a^b mod c{ long long ret = 1; a %= c; for (; b; b >>= 1, a = multi(a, a, c)) if (b & 1) ret = multi(ret, a, c); return ret;}int main(){ int cas = 0; long long n; while(scanf("%I64d", &n) != EOF && n) { int k = 0; while(n % 2 == 0) { n /= 2; k++; } if(k > 3 || n % 5 == 0) { printf("Case %d: 0\n", ++cas); continue; } n = n * 9LL; long long len = euler(n); long long ans = 100000000000LL; for(long long i = 1LL; i * i <= len; i++) { if(len % i == 0) { long long f = len / i; if(fastmod(10LL, i, n) == 1LL) ans = min(ans, i); if(fastmod(10LL, f, n) == 1LL) ans = min(ans, f); } } if(ans == 100000000000LL) ans = 0; printf("Case %d: %I64d\n", ++cas, ans); } return 0;}