自动搬运

查看原文

来自洛谷，原作者为

	fish_love_cat 「要毁灭世界，根本不需要邪恶。起初，那些都是不会被任何人怪罪的小小愿望。而那样的愿望却如此轻易地，和末日相连在一起。」

搬运于2025-08-24 23:14:13，当前版本为作者最后更新于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$ 是最小解矛盾。

于是原命题得证。