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

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

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

输入格式

输入包含多组测试用例。

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

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

输出格式

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

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

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

数据范围

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

输入样例：

输出样例：

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=;

    while(b){

        if(b&) ans=(ans*a)%c;

        b=b/;

        a=(a*a)%c;

    }

    return ans;

}

ll phi(ll x){

    ll sum=x;

    for(int i=;i<=sqrt(x);i++){

        if(x%i!=) continue;

        sum=sum/i*(i-);

        while(x%i==) x/=i;

    }

    if(x>) sum=sum/x*(x-);

    return sum;

}

int main(){

    ll n;

    ll num=;

    while(cin>>n){

        if(n==) break;

        ll z=n/__gcd(n,(ll))*;

        ll x=phi(z);

        ll ans=MAX;

        for(int j=;j*j<=x;j++){

            if(x%j!=) continue;

            if(quick_pow(,j,z)==) ans=min(ans,(ll)j);

            if(quick_pow(,x/j,z)==) ans=min(ans,(ll)x/j);

        }

        if(ans==MAX) ans=;

        cout<<"Case "<<num++<<": "<</*ans==MAX?(ll)0:*/ans<<endl;

    }

}

巴特西

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

输入格式

输出格式

数据范围

输入样例：

输出样例：

最新文章

热门文章

巴特西

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

输入格式

输出格式

数据范围

输入样例：

输出样例：

最新文章

热门文章

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