题解：P10496 The Luckiest Number

liuliucy · 2024-07-08 21:03:12 · 题解

思路

首先，我们先把 lucky number 表示出来。

那根据题目条件，也就是 9L|8\times (10^{n}-1)。

因为 \gcd(9,8)=1 ，

所以另 d=\gcd(L,8)。

那我们可以有 \frac{9L}{d}|10^{n}-1，

另 x=\frac{9L}{d}，

我们有 10^{n}\equiv 1(\mod x)，这里其实可以直接用 BSGS 求解了，但这里我们也可以用另外一种方法。

根据欧拉定理，我们可以知道 \varphi(x) 是一个解，但我们要求最小的 n，我们可以知道 n|\varphi(n) ，因为假如存在最小的 n 使得 10^n\equiv10^{\varphi(x)}\equiv 1(\mod x)，则 10^{\varphi(x)\mod n}\equiv1(\mod x)，显然 \varphi(x)\mod n< n，我们找到了一个更小的，所以假设不成立，命题得证。

我们只需要先求出 \varphi(x) 再枚举他的因数进行判断即可，复杂度 \mathcal{O}(\sqrt n \log n)

CODE

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n;
const int N=1e6;
int phi(int x){
    int ans=x,t=x;
    for(int i=2;i*i<=x;i++){    
        if(t%i!=0)continue;
        ans=ans/i*(i-1);
        while(t%i==0)t/=i;
    }
    if(t>1)ans=ans/t*(t-1);
    return ans;
}//求欧拉函数
int qw(int a,int b,int md){
    if(b==0)return 1;
    int res=qw(a,b/2,n);
    res=res*res%md;
    if(b%2==1)res=res*a%md;
    return res;
}
signed main(){
    int t=0;
    while(scanf("%lld",&n)){
        t++;
        if(n==0)return 0;
        int d=__gcd(8ll,n),ans=1e18;
        n=9*n/d;
        if(n%2==0||n%5==0){
            printf("Case %lld: 0\n",t);
            continue;
        }//答案不存在
        int x=phi(n);
        ans=x;
        for(int i=1;i*i<=x;i++){
            if(x%i!=0)continue;
            if(qw(10,i,n)%n==1)ans=min(ans,i);
            if(qw(10,x/i,n)%n==1)ans=min(ans,x/i);//枚举phi(x)的因子
        }
        if(ans==1e18)ans=0;
        printf("Case %lld: %lld\n",t,ans);
    }
    return 0;
}