标签：Luckiest 10 gcd pmod 题解 number long int equiv

很容易想到，\(n\)个8可以转换为\((10^{n+1}-1)/9*8\)

容易你个集贸啊，xzz推10分钟我推了一个上午

顺便膜拜xzz

然后就是推式子了。。。(悲

\[(10^{n+1}-1)/9*8\equiv 0\pmod h\\ =>{10^{n+1}*8-8\above 1pt9}\equiv 0\pmod h\\ =>10^{n+1}*8-8\equiv 0\pmod {9h}\\ =>10^{n+1}*8\equiv 8\pmod {9h}\\ =>10^{n+1}\equiv 1\pmod{{9h\above 1pt gcd(8,h)}} \]

PS:推到最后一步时我认为要拿while处理，xzz告诉我有个东西叫gcd，我惊讶极了

然后就可以欧拉定理了

PS*2：欧拉定理和万恶的高斯消元一样，只能求出特解，要枚举解的因子

最后贴上丑陋的代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt,n;
int phi_(int x){
	double ans=x;
	for(int i=2;i<=sqrt(x);i++){
		if(x%i==0){
			ans=ans*(i-1)/i;
		}
		while(x%i==0){
			x/=i;
		}
	}
	if(x!=1){
		ans=ans*(x-1)/x;
	}
	return ans;
}
int qpow(int a,int b,int mod){
	int ans=1;
	while(b){
		if(b&1){
			ans=(ans%mod*a%mod+mod)%mod;
		}
		a=(a%mod*a%mod+mod)%mod;
		b>>=1;
	}
	return ans%mod;
}
signed main(){
	while(cin>>n&&n){
		n*=9;
		n=n/(__gcd((long long)8,n));
		if(__gcd(n,(long long)10)>1){
			cout<<"Case "<<++cnt<<":"<<0<<endl;
			continue;
		}
		int phi=phi_(n),minn=1e9;
		for(int i=1;i*i<=phi;i++){
			if(phi%i){
				continue;
			}
			if(qpow(10,i,n)==1){
				minn=min(i,minn);
			}
			if(qpow(10,phi/i,n)==1){
				minn=min(phi/i,minn);
			}
		}
		cout<<"Case "<<++cnt<<":"<<minn<<endl;
	}
	return 0;
}

poj3696 The Luckiest number

标签：Luckiest,10,gcd,pmod,题解,number,long,int,equiv
From： https://www.cnblogs.com/lewisak/p/18146983