题解：P10496 The Luckiest Number

_HCl_ · 2024-07-08 21:06:11 · 题解

有趣的数论题。

P10496 题解

题意简述

给定一个正整数 L。问至少多少个 8 连在一起组成的正整数是 L 的倍数？

思路引导

我们先将 n-1 个 8 连成的数表达出来。

众所周知 10^{n}-1=\overline{99\dots9}, 故 \overline{11\dots1}=\frac{10^{n}-1}{9}, 则 \overline{88\dots8}=\frac{8}{9}(10^{n}-1)。

然后有

我们将问题转化为了求解最小的 n，可以使用 BSGS 进行求解，但是我不会。所以考虑欧拉定理。方便表述，记 d=\frac{9L}{\gcd(8,L)}。

根据欧拉定理，n=\varphi(d) 显然是其中的一个解，但是这不是最小的。观察发现最小的 n 一定是 \varphi(d) 的因数。下证成立。

假设 a^x\equiv1\pmod d 的最小解 x_0 不是 p=\varphi(d) 的因数。设 x_0=qp+r, 其中 0<r<p。那么有（为方便书写，以下同余式 \pmod d 均省略）：

由于 r<x_0，所以 x_0 不是最小的解，与假设矛盾。故原命题得证。

因此，只需要枚举 \varphi(d) 的每一个因数，计算是否满足 10^n\equiv 1\pmod d，找出最小值即可。

时间复杂度 \mathcal{O}(\sqrt n)。

代码

感觉自己代码写的算是比较清楚，就不写注释了，应该都看的懂的。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int L,MOD;
int phi(int x){
    int res=x;
    for(int i=2;i*i<=x;++i)
        if(x%i==0){
            res=res-res/i;
            while(x%i==0)x/=i;
        }
    if(x!=1)return res-res/x;
    else return res;
}
int qpow(int x,int y){
    int res=1;
    for(;y;y>>=1,x=(x*x)%MOD)if(y&1)res=res*x%MOD;
    return res;
}
signed main(){
    int L,id=0;
    cin>>L;
    while(L!=0){
        id++;
        int d=9ll*L/__gcd(L,8ll),p=phi(d),ans=1e9;
        MOD=d;
        for(int i=1;i*i<=p;++i){
            if(p%i)continue;
            if(qpow(10,i)==1)ans=min(ans,i);
            if(qpow(10,p/i)==1)ans=min(ans,p/i);
        }
        if(ans>=1e9)ans=0;
        cout<<"Case "<<id<<": "<<ans<<"\n";
        cin>>L;
    } 
}