AcWing 202. 最幸运的数字 （欧拉定理）打卡

8是中国的幸运数字，如果一个数字的每一位都由8构成则该数字被称作是幸运数字。

现在给定一个正整数L，请问至少多少个8连在一起组成的正整数（即最小幸运数字）是L的倍数。

输入格式

输入包含多组测试用例。

每组测试用例占一行，包含一个整数L。

当输入用例L=0时，表示输入终止，该用例无需处理。

输出格式

每组测试用例输出结果占一行。

结果为“Case 1: ”+一个整数N，N代表满足条件的最小幸运数字的位数。

如果满足条件的幸运数字不存在，则N=0。

数据范围

1≤L≤2∗1091≤L≤2∗109

输入样例：

8
11
16
0

输出样例：

Case 1: 1
Case 2: 2
Case 3: 0


题意：找到满足最小的满足要求的长度8，要求能被L整除
思路：首先我们可以化简式子   
 8*（10^x-1）/9 | L   ->  8*（10^x-1）| 9*L     ->   （10^x-1） | 9*L/gcd(L,8)   ->    10^x  = 1 mod 9*L/gcd(L,80) 

 化简到这种式子后我们一般有两个定理可以运用
费马小定理   
如果a,p互质   a^p  = a mod p

欧拉定理   
如果  a，p 互质   a^phi(p) = 1 mod p;
phip) 不一定 是最优的答案，有可能是他的因子，所以我们还要枚举他的因子

#include<bits/stdc++.h>
#define maxn 305
#define mod 1000000007
#define MAX 100000000000000000
using namespace std;
typedef long long ll;
ll quick_pow(ll a,ll b,ll c){
    ll ans=1;
    while(b){
        if(b&1) ans=(ans*a)%c;
        b=b/2;
        a=(a*a)%c;
    }    
    return ans;
}
ll phi(ll x){
    ll sum=x;
    for(int i=2;i<=sqrt(x);i++){
        if(x%i!=0) continue;
        sum=sum/i*(i-1);
        while(x%i==0) x/=i;
    } 
    if(x>1) sum=sum/x*(x-1);
    return sum; 
}
int main(){
    ll n;
    ll num=1;
    while(cin>>n){
        if(n==0) break;
        ll z=n/__gcd(n,(ll)8)*9; 
        ll x=phi(z);
        ll ans=MAX;
        for(int j=1;j*j<=x;j++){
            if(x%j!=0) continue;
            if(quick_pow(10,j,z)==1) ans=min(ans,(ll)j);
            if(quick_pow(10,x/j,z)==1) ans=min(ans,(ll)x/j); 
        }
        if(ans==MAX) ans=0;
        cout<<"Case "<<num++<<": "<</*ans==MAX?(ll)0:*/ans<<endl;
    }
}