The Luckiest number
题意：给一个数L，问至少几个8（如88，8888，88888）可以整数L。若不能，就输出-1.
参考的两位dalao的
http://blog.csdn.net/Danliwoo/article/details/48865127
http://blog.csdn.net/whai362/article/details/43908013
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #include <iostream> 5 #include <cmath> 6 using namespace std; 7 #define ll long long 8 //const int maxn=44725; //sqrt(2000000000)=44721.4 9 //int pri[maxn]; 10 //int cnt; 11 /* 12 void init(){ 13 cnt=0; 14 memset(pri,0,sizeof(pri)); 15 for(ll i=2;i<maxn;i++) if(!pri[i]){ 16 pri[cnt++]=i; 17 for(ll j=i*i;j<maxn;j+=i) pri[j]=1; 18 } 19 } 20 */ 21 ll L; 22 ll gcd(ll a,ll b){ 23 return b==0?a:gcd(b,a%b); 24 } 25 26 ll phi(ll x){ 27 ll ans=x; 28 int m=sqrt(x+0.5); 29 for(int i=2;i<=m;i++) if(x%i==0){ 30 ans=ans/i*(i-1); 31 while(x%i==0) x/=i; 32 } 33 if(x>1) ans=ans/x*(x-1); 34 return ans; 35 } 36 ll quickadd(ll a,ll b,ll m){ 37 ll temp=a%m,res=0; 38 while(b){ 39 if(b&1) res=(res+temp)%m; 40 b>>=1; 41 temp=(temp+temp)%m; 42 } 43 return res; 44 } 45 ll quickpow(ll a,ll b,ll m){ 46 ll temp=a%m,res=1; 47 while(b){ 48 if(b&1) res=quickadd(res,temp,m); 49 b>>=1; 50 temp=quickadd(temp,temp,m); 51 } 52 return res; 53 } 54 int main(){ 55 int kase=0; 56 // init(); 57 while(scanf("%lld",&L)&&L){ 58 ll m=L*9/gcd(L,8); 59 printf("Case %d: ",++kase); 60 if(gcd(m,10)!=1) puts("0"); 61 else{ 62 ll ph=phi(m); 63 int lim=sqrt(ph); 64 ll ans=ph; 65 for(ll i=1;i<=lim;i++){ 66 if(ph%i==0){ 67 if(quickpow(10,i,m)==1) ans=min(ans,i); 68 else if(quickpow(10,ph/i,m)==1) ans=min(ans,ph/i); 69 } 70 } 71 printf("%lld ",ans); 72 } 73 } 74 return 0; 75 }