首页 > 代码库 > POJ 3696

POJ 3696

2024-07-22 05:15:44   215人阅读

这里面的一个转换的小技巧很重要，把888...8转换成(10^x-1)/9*8。神来之笔，佩服。

这样有(10^x-1)/9*8=L*p得10^x-1=L*p*9/8，设m=9*L/gcd(L,8)。这一步如何想到的呢？其实是为了使m与10互质而做的。因为这样必有m*p1=10^x-1。使得同余方程

10^x=1 mod m，相信到了这一步，都知道用欧拉定理了。于是只需求出phi(m)，枚举其因子，使得同余方程成立即可

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <cmath>#define LL __int64using namespace std;LL gcd(LL a,LL b){	if(b==0) return a;	return gcd(b,a%b);}LL fac[10000]; int cnt;LL Euler(LL m){	LL res=m;	LL k=(LL)sqrt((double)m);	for(LL i=2;i<=k;i++){		if(m%i==0){			res=res-res/i;			while(m%i==0)			m/=i;		}	}	if(m>1)	res=res-res/m;	return res;}LL multi(LL a,LL b,LL m){    LL ret=0;    while(b>0){        if(b&1) ret=(ret+a)%m;        b>>=1;        a=(a<<1)%m;    }    return ret;}LL quick(LL a,LL k,LL m){	LL ans=1;	while(k){		if(k&1)		ans=multi(ans,a,m);		k=(k>>1);		a=multi(a,a,m);	}	return ans;}int main(){	LL l; int kase=0; 	while(scanf("%I64d",&l),l){		if(l%16==0||l%5==0) {			printf("Case %d: 0\n",++kase);			continue;		}		cnt=0;		LL m=l*9/gcd(l,(LL)8);		LL phi=Euler(m);		LL ans;		LL k=(LL)sqrt((double)phi);		for(LL i=1;i<=k;i++){			if(phi%i==0){				fac[cnt++]=i;				fac[cnt++]=phi/i;			}		}		sort(fac,fac+cnt);		for(int i=0;i<cnt;i++){			ans=quick((LL)10,fac[i],m);			if(ans==1){				printf("Case %d: %I64d\n",++kase,fac[i]);				break;			}		}	}	return 0;}

　　

POJ 3696


联系
我们