poj 3696 The Luckiest number

题目大意：

给你一个L，问多少个连续的8是L的倍数。L<=2000000000

思路：

我们要求
L|8*（10^x-1）/9
9L|8*（10^x-1）
我们设GCD(8，L)为d
9L/d|10^x-1
10^x=1（mod 9L/d）

这样就变成求一个同余方程的最小解了。
还有一个定理，对于a^x=1(mod n) ，如果存在，那么x一定是fai（n）的因数，（可通过费马小定理，欧拉定理感性理解）。对于每一个因数快速幂判断就好了。

！！
黑科技，因为本题范围很大，要用到LONG LONG的乘法mo。c++没有这么大的整形变量。方法如下

程序：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define LL long long 
#define N 1000
using namespace std;
LL a[N];
LL s,mo,n;
LL fai(LL x){
    int i=1;
    while (a[i]!=0) {
        a[i]=0;
        i++;
    }
    int j=1;
    i=2;
    LL fai=x;
    while (i*i<x){
        if (x%i==0) {
            a[j]=i;
            x=x/i;
        } else {
            i++;
            if (a[j]) j++;
        }
    }
    fai=fai/x*(x-1);
    for (int i=1;i<=j;i++)
     if (a[i]) fai=fai/a[i]*(a[i]-1);
    return fai;
}

LL gcd(LL x,LL y){
    if (y==0) return x;
    return gcd(y,x%y);
}

LL momo(LL a,LL b,LL MOD)
{
    LL tmp=a*b-(LL)((long double)a/MOD*b+1e-8)*MOD;
    if (tmp<0) tmp+=MOD;
    return tmp;
}

LL mul(LL x,LL y){
    LL ans=1;
    while (y){
        if (y&1) ans=momo(ans,x,mo);
        y>>=1;
        x=momo(x,x,mo);
    }
    return ans;
}

int main(){
    scanf("%lld",&n);
    LL h=0;
    while (n){
        LL ans=1200000000000,o=1;h++;
        mo=(9*n)/(gcd(8,n));
        s=fai(mo);
        for (LL i=1;i*i<=s;i++)
        if (s%i==0){
                if (mul(10,i)==1) ans=min(ans,i);
                if (mul(10,s/i)==1) ans=min(ans,s/i);
        }
        printf("Case %lld: ",h);
        if (ans==1200000000000) ans=0;
        cout<<ans<<endl;

        scanf("%lld",&n);
    }
}