解析

題意可以化為：
$$8?\frac{10^x?1}{9}+kn=0$$
然后用 8 盡可能的消去 $9n$ 中的2的冪次，隨后問題轉化為：
$$10^x\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\prime })$$
然后…我就覺得這個是exbsgs了…
但其實完全不用阿！

這個東西就是求 $10$ 在模 $n^{\prime }$ 意義下的階。
首先，無解的充要條件是 $\gcd (10,n^{\prime })>1$。
否則，答案必然是 $\phi (n^{\prime })$ 的因數，因為 $10^{\phi (n^{\prime })}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}{n}^{\prime })$。
暴力檢驗即可。
注意會爆 long long

代碼

#include<bits/stdc++.h> using namespace std; #define ll __int128 #define debug(...) fprintf(stderr,__VA_ARGS__) #define OK debug("OK\n") inline ll read(){ll x(0),f(1);char c=getchar();while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}while(isdigit(c)){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f; }const int N=1e7+100; const int mod=998244353;inline ll ksm(ll x,ll k,ll mod){ll res(1);while(k){if(k&1) res=res*x%mod;x=x*x%mod;k>>=1;}return res; }int n,m;int prime[N/10],tot; bool vis[N]; void init(){int n=1e7;for(int i=2;i<=n;i++){if(!vis[i]){prime[++tot]=i;}for(int j=1;j<=tot&&prime[j]<=n/i;j++){int now=prime[j];vis[now*i]=1;if(i%now==0){break;}}} return; }ll calc(ll n){ll res=n,x=n;for(int i=2;1ll*i*i<=n;i++){if(x%i) continue;res=1ll*res/i*(i-1);while(x%i==0) x/=i;}if(x>1) res=1ll*res/x*(x-1);return res; }inline ll gcd(ll x,ll y){return y?gcd(y,x%y):x; } ll find(ll phi,ll mod){if(gcd(10,mod)>1) return 0;ll ans=2e18;for(ll i=1;i*i<=phi;i++){if(phi%i) continue;if(ksm(10,i,mod)==1) ans=min(ans,i);if(ksm(10,phi/i,mod)==1) ans=min(ans,phi/i);}return ans; }signed main(){ #ifndef ONLINE_JUDGEfreopen("a.in","r",stdin);freopen("a.out","w",stdout); #endifint clo(0);while(1){ll n=read()*9;if(!n) break;for(int i=1;i<=3&&n%2==0;i++) n>>=1;ll phi=calc(n);printf("Case %d: %lld\n",++clo,(long long)find(phi,n));}return 0; } /* */

總結

以上是生活随笔為你收集整理的YBTOJ：最小数（欧拉函数）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。