http://poj.org/problem?id=3696
这个题挺好,开始以为只要是素因子分解后2的幂次不超过3并且该数 / 2^x后这个数必须是11111111…… 的形式几个1就输出几,然后我脑残的写交了然后就脑残的wa 了……才发现11111……不一定都是素数。。。
正解是: 10^n =1 (mod gcd(8,l)*9*l) 满足条件最小值,个人比较懒就不证明了,就是所谓的元根
注意这个题目 一般的快速幂还不行,可以超过int 后自乘就溢出了
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> using namespace std; typedef long long ll; ll prime[1100],factor[1100000]; int num[1100],cnt,fac_n; ll gcd(ll a, ll b) { if(a==0) return 1; if(a<0) return gcd(-a,b); return b==0?a:gcd(b,a%b); } ll phi(ll a) { ll ret=a; for(ll i=2;i*i<=a;i++) if(a%i==0) { ret=ret/i*(i-1); while(a%i==0) a/=i; } if(a!=1) ret=ret/a*(a-1); return ret; } void dfs(int id,ll mul) { if(id==cnt) { factor[fac_n++]=mul; return; } ll tmp=1; for(int i=0;i<=num[id];i++) { dfs(id+1,mul*tmp); tmp*=prime[id]; } } ll mod1(ll a,ll b,ll m)//计算a*b%m { ll ret=0; while(b) { if(b&1) { ret+=a; if(ret>=m) ret-=m; } a+=a; if(a>=m) a-=m; b>>=1; } return ret; } bool quick_pow(ll a,ll mod) { ll ans=1,b=10; while(a) { if(a&1) ans=mod1(ans,b,mod); a>>=1; b=mod1(b,b,mod); } return ans==1; } int main() { int cas=1; ll L; while(scanf("%lld",&L)==1&&L) { ll gd=gcd(9*L,8); ll m=9*L/gd; if(m%2==0||m%5==0) { printf("Case %d: 0\n",cas++);continue;} ll ph=phi(m); cnt=0; for(ll i=2;i*i<=ph;i++) if(ph%i==0) { prime[cnt]=i; int tmp=0; while(ph%i==0) tmp++,ph/=i; num[cnt++]=tmp; } if(ph!=1) prime[cnt]=ph,num[cnt++]=1; fac_n=0; dfs(0,1); sort(factor,factor+fac_n); for(int i=0;i<fac_n;i++) { if(quick_pow(factor[i],m)) { printf("Case %d: %lld\n",cas++,factor[i]); break; } } } return 0; }