题解：P12272 [蓝桥杯 2024 国 Python B] 全 X 数

fish_love_cat · 2025-07-03 21:09:03 · 题解

诶等大可的题解怎么失踪了，那我来写一篇。

三倍经验：P10496，P12272，AT_abc222_g

假设有一个长度为 t 每一位都为 9 的数字，我们可以这么表示它：

然后将这个数字乘上 9^{-1}x，就得到了等长的每一位都为 x 的数字，也就是：

根据题面，这个数是 n 的倍数，于是有：

转化：

设 d=\gcd(x,9n)，于是有：

设 P=\frac{9n}{d}，那么也就是说：

现在你想怎么做都可以，比如使用 BSGS。

但你如果和我一样 BSGS 忘了怎么处理了怎么办呢？

你需要知道这么一个东西：

若 a\perp p，那么 a^x\equiv 1\pmod p 的最小整数解满足 x\mid\varphi(p)。

证明放在文末。

那么我们只需要对于每一个 x 求出 P，然后对于 \varphi(P) 的每一个约数进行检测，然后选最小就能求出长度。

做完了。记得开 __int128。

#include<bits/stdc++.h>
#define int __int128
#define mod 998244353
using namespace std;
int read(){
    int sum=0,fish=1;
    char c=getchar_unlocked();
    while((c<'0'||c>'9')&&c!='-')c=getchar_unlocked();
    if(c=='-')fish=-1,c=getchar_unlocked();
    while(c>='0'&&c<='9')sum=sum*10+(c-'0'),c=getchar_unlocked();
    return sum*fish;
}
void print(int x){
    if(x<0)putchar_unlocked('-'),x=-x;
    if(x<10)putchar_unlocked(x+'0');
    else print(x/10),putchar_unlocked(x%10+'0');
}
#define flc_INF LLONG_MAX
int qpow(int a,int b,int p=flc_INF){
    int ans=1;
    if(b==0)return 1;
    while(b){
        if(b&1)ans*=a,ans%=p;
        a*=a,b>>=1,a%=p;
    }
    return ans;
}
int phi(int n){
    int ret=n;
    for(int i=2;i*i<=n;i++){
        if(n%i==0)ret=ret/i*(i-1);
        while(n%i==0)n/=i;
    }
    if(n==1)return ret;
    return ret=ret/n*(n-1);
}
int T=1e18,X;
signed main(){
    int n=read();n*=9;
    for(int i=1;i<=9;i++){
        int m=n/__gcd(n,i);
        int p=phi(m);
        int mini=1e18;
        for(int j=1;j*j<=p;j++)
        if(p%j==0){
            if(qpow(10,j,m)==1)mini=min(mini,j);
            if(j*j==p)continue;
            if(qpow(10,p/j,m)==1)mini=min(mini,p/j);
        }
        if(T>mini)T=mini,X=i;
    }
    if(T==1e18)cout<<-1;
    else print(qpow(9,mod-2,mod)*(qpow(10,T,mod)-1)%mod*X%mod);
    return 0;
}

证明：

考虑反证法。

若 x\nmid\varphi(p)，那么 \varphi(p)=kx+b，此处 a<x。

因为 a^x\equiv1\pmod p，所以 a^{kx}\equiv1\pmod p。

因为欧拉定理 a^{\varphi(p)}\equiv1\pmod p，所以 a^{kx+b}\equiv1\pmod p。

我们把这两个柿子除一下，于是就有 a^b\equiv 1\pmod p，这与 x 是最小解矛盾。

于是原命题得证。