The Luckiest number（hdu2462）

The Luckiest number

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1163 Accepted Submission(s): 363

Problem Description

Chinese people think of '8' as the lucky digit. Bob also likes digit '8'. Moreover, Bob has his own lucky number L. Now he wants to construct his luckiest number which is the minimum among all positive integers that are a multiple of L and consist of only digit '8'.

Input

The input consists of multiple test cases. Each test case contains exactly one line containing L(1 ≤ L ≤ 2,000,000,000).

The last test case is followed by a line containing a zero.

Output

For each test case, print a line containing the test case number( beginning with 1) followed by a integer which is the length of Bob's luckiest number. If Bob can't construct his luckiest number, print a zero.

Sample Input

Sample Output

Case 1: 1

Case 2: 2

Case 3: 0

思路：欧拉函数；

其实这题和hdu3307，基本一样，只不过这个推下。

设f[n],表示n位全是8的数，那么f[n]=10*f[n-1]+8,那么构造等比数列f[n]+(8/9)=10*(f[n-1]+(8/9));

那么f[n] = (8+8/9)*(10)^(n-1)-8/9;f[n] = (8/9)*（(10)^n-1）;那么就是要求最小的n使f[n]%L=0;

那么(8/9)*（10^n-1）=k*L;

8/gcd(8,L)*（10^n-1）=9*k*L/(gcd(8,L));

化简为8/gcd(8,L)*（10^n）%（9*L/(gcd(8,L))）=8/gcd（8，L）;

8/gcd（8，L）与（9*L/(gcd(8,L))互质可以消去，的10^n%（9*L/(gcd(8,L))）=1;

那么用另模数为m，10^n%（m）=1;

m和10必定互质，否则无解。

于是根据欧拉定理，10^(Euler(m)) = 1(mod m) 。由于题目要求最小的解，解必然是Euler(m)的因子。

需要注意的是，对于10^x，由于m太大，直接快速幂相乘的时候会超long long

这题我开始用baby-step,超时了；

  1 #include<stdio.h>
  2 #include<algorithm>
  3 #include<iostream>
  4 #include<string.h>
  5 #include<queue>
  6 #include<set>
  7 #include<math.h>
  8 #include<map>
  9 using namespace std;
 10 typedef long long LL;
 11 pair<LL,LL>exgcd(LL n,LL m);
 12 LL gcd(LL n,LL m);
 13 LL quick(LL n,LL m,LL mod);
 14 LL mul(LL n, LL m,LL p);
 15 int  slove(LL n);
 16 LL phi(LL n);
 17 bool prime[1000005];
 18 int ans[1000005];
 19 LL fen[1000005];
 20 int main(void)
 21 {
 22         LL n;
 23         int i,j;
 24         int cn = 0;
 25         for(i = 2; i <= 1000; i++)
 26         {
 27                 if(!prime[i])
 28                 {
 29                         for(j = i; (i*j) <= 1000000; j++)
 30                         {
 31                                 prime[i*j] = true;
 32                         }
 33                 }
 34         }
 35         for(i = 2; i <= 1000000; i++)
 36         {
 37                 if(!prime[i])
 38                 {
 39                         ans[cn++] = i;
 40                 }
 41         }
 42         //printf("%d
",cn);
 43         int __ca = 0;
 44         while(scanf("%lld",&n),n!=0)
 45         {
 46                 LL gc = gcd(8,n);
 47                 n = 9*n/gc;
 48                 LL oula = phi(n);
 49                 LL x = gcd(n,10);//printf("%lld
",n);
 50                 //printf("%lld
",x);
 51                 printf("Case %d: ",++__ca);
 52                 if(x!=1)
 53                 {
 54                         printf("0
");
 55                 }
 56                 else
 57                 {
 58                         int k = slove(oula);
 59                         //printf("%d
",k);
 60                         for(i = 0;i < k;i++)
 61                         {
 62                              LL akk =quick(10,fen[i],n);
 63                              if(akk==1)
 64                              {
 65                                  break;
 66                              }
 67                         }//printf("%d
",10);
 68                         printf("%lld
",fen[i]);
 69                 }
 70         }
 71         return 0;
 72 }
 73 int  slove(LL n)
 74 {   int cn = 0;int i,j;
 75     for(i = 1;i < sqrt(1.0*n);i++)
 76     {
 77         if(n%i==0)
 78         {
 79             if(n/i==i)
 80             {
 81                 fen[cn++] = i;
 82             }
 83             else
 84             {
 85                 fen[cn++] = i;
 86                 fen[cn++] = n/i;
 87             }
 88         }
 89     }
 90     sort(fen,fen+cn);
 91     return cn;
 92 }
 93 LL phi(LL n)
 94 {
 95         int f = 0;
 96         bool flag = false;
 97         LL ask =n;
 98         while(n>1)
 99         {
100                 while(n%ans[f]==0)
101                 {
102                         if(!flag)
103                         {
104                                 flag = true;
105                                 ask/=ans[f];
106                                 ask*=ans[f]-1;
107                         }
108                         n/=ans[f];
109                 }
110                 f++;
111                 flag = false;
112                 if((LL)ans[f]*(LL)ans[f]>n)
113                 {
114                         break;
115                 }
116         }
117         if(n > 1)
118         {
119                 ask/=n;
120                 ask*=(n-1);
121         }
122         return ask;
123 }
124 pair<LL,LL>exgcd(LL n,LL m)
125 {
126         if(m==0)
127                 return make_pair(1,0);
128         else
129         {
130                 pair<LL,LL>ak = exgcd(m,n%m);
131                 return make_pair(ak.second,ak.first-(n/m)*ak.second);
132         }
133 }
134 LL gcd(LL n,LL m)
135 {
136         if(m==0)
137                 return n;
138         else return gcd(m,n%m);
139 }
140 LL quick(LL n,LL m,LL mod)
141 {
142         LL ak = 1;
143         n %= mod;
144         while(m)
145         {
146                 if(m&1)
147                         ak =mul(ak,n,mod);
148                 n = mul(n,n,mod);
149                 m>>=1;
150         }
151         return ak;
152 }
153 LL mul(LL n, LL m,LL p)
154 {
155         n%=p;
156         m%=p;
157         LL ret=0;
158         while(m)
159         {
160                 if(m&1)
161                 {
162                         ret=ret+n;
163                         ret%=p;
164                 }
165                 m>>=1;
166                 n<<=1;
167                 n%=p;
168         }
169         return ret;
170 }

油！油！you@