poj3696 The Luckiest number 数论好题
#include<iostream>#include<cstdlib>#include<stdio.h>#include<algorithm>#define ll __int64using namespace std;ll p[10000],cnt[10000];ll fac[100000];ll cc,s;ll phi(ll n){ ll ans=1,i; for(i=2;i*i<=n;i++) { if(n%i==0) { n/=i; ans*=i-1; while(n%i==0) { n/=i;ans*=i; } } } if(n>1) ans*=n-1; return ans;}void split(ll x){ cc=0; for(ll i=2;i*i<=x;i++) { if(x%i==0) { p[cc]=i; int count=0; while(x%i==0) { count++;x/=i; } cnt[cc]=count; cc++; } } if(x>1) { p[cc]=x;cnt[cc]=1;cc++; }}void dfs(ll count,ll step){ if(step==cc) { fac[s++]=count; return ; } ll sum=1; for(int i=0;i<cnt[step];i++) { sum*=p[step]; dfs(count*sum,step+1); } dfs(count,step+1);}ll mul(ll a,ll b,ll m){ ll res=0; while(b) { if(b&1) res+=a; if(res>m) res-=m; a+=a; if(a>m) a-=m; b>>=1; } return res;}ll pow(ll a,ll b,ll m){ ll res=1; while(b) { if(b&1) res=mul(res,a,m); a=mul(a,a,m); b>>=1; } return res;}ll gcd(ll a,ll b){ if(b==0) return a; return gcd(b,a%b);}int main(){ int count=1; ll n; while(scanf("%I64d",&n)&&n) { printf("Case %d: ",count++); ll M=9*n/gcd(n,8); if(gcd(10,M)!=1) {puts("0");continue;} ll m=phi(M); split(m); s=0; dfs(1,0); sort(fac,fac+s); for(int i=0;i<s;i++) { if(pow(10,fac[i],M)==1) { cout<<fac[i]<<endl; break; } } } return 0;}
