POJ 3696 The Luckiest number （欧拉函数，好题）

该题没思路，参考了网上各种题解。。。。

注意到凡是那种11111..... 22222..... 33333.....之类的序列都可用这个式子来表示：k*(10^x-1)/9
进而简化：8 * (10^x-1)/9=L * k (k是一个整数)
8*(10^x-1)=9L*k
d=gcd(9L,8)=gcd(8,L)
8*(10^x-1)/d=9L/d*k
令p=8/d q=9L/d p*(10^x-1)=q*k
因为p,q互质，所以q|(10^x-1)，即10^x-1=0(mod q)，也就是10^x=1(mod 9*L/d)
由欧拉定理可知，当q与10互质的时候，10^(φ(q))=1 (mod q)，即必定存在一个解x。
而题目中要求的是最小的解，设为min，那么有a^min=1%q，因为要满足a^φ(q)=1%q，那么a^φ(q)肯定能变换成(a^min)^i。
所以接下来只要枚举φ(q)的因子，找出符合条件的最小者即可。

无解的时候就是q与10不互质的时候，因为若q与10有公因子d：
1.若d=2，q=2*k，那么10^x=2^x*5^x=1%2k
   即2^x*5^x=1+2k*m，左边为偶数，右边为奇数，显然矛盾。
2.若d=5，q=5*k，那么10^x=2^x*5^x=1%5k
   即2^x*5^x=1+5k*m，左边是5的倍数，右边不是5的倍数，显然矛盾。

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
long long L;

long long gcd(long long a,long long b) {
    return b==0?a:gcd(b,a%b);
}
long long multi(long long a,long long b,long long mod) {
    long long ret=0;
    while(b) {
        if(b&1)
            ret=(ret+a)%mod;
        a=(a<<1)%mod;
        b=b>>1;
    }
    return ret;
}
long long quickPow(long long a,long long b,long long mod) {
    long long ret=1;
    while(b) {
        if(b&1)
            ret=multi(ret,a,mod);  //直接相乘的话可能会溢出
        a=multi(a,a,mod);
        b=b>>1;
    }
    return ret;
}
//求欧拉函数
long long eular(long long n) {
    long long ret=1,i;
    for(i=2; i*i<=n; i++) {
        if(n%i==0) {
            n=n/i;
            ret*=i-1;
            while(n%i==0) {
                n=n/i;
                ret*=i;
            }
        }
    }
    if(n>1)
        ret*=n-1;
    return ret;
}

int main() {
    int t=0;
    while(scanf("%I64d",&L)!=EOF) {
        if(L==0)
            break;
        long long p=9*L/gcd(L,8);
        long long d=gcd(10,p);
        if(d==1) {
            long long phi=eular(p);
            long long ans=phi;
            long long m=sqrt((double)phi);
            bool flag=false;
            //先枚举大小在1~sqrt(phi)之间的因子
            for(int i=1; i<=m; i++) {
                if(phi%i==0 && quickPow(10,i,p)==1) {
                    ans=i;
                    flag=true;
                    break;
                }
            }
            //若1~sqrt(phi)没找到符合的因子，那么枚举sqrt(phi)~phi之间的因子
            if(!flag) {
                for(int i=m; i>=2; i--) {
                    if(phi%i==0 && quickPow(10,phi/i,p)==1) {
                        ans=phi/i;
                        break;
                    }
                }
            }
            printf("Case %d: %I64d
",++t,ans);
        } else {
            printf("Case %d: 0
",++t);
        }
    }
    return 0;
}