http://poj.org/problem?id=36968*10^0+8*10^1+8*10^2+8*10^3+8*10^4+.....+8*10^(n-1) = 8*(10^n-1)/9
由题意有 8 * ( 10^n - 1 ) / 9 = 0 ( mod L ) 求最小的 n
-------> 8 * ( 10^n - 1 ) = 0 ( mod 9 * L )
-------> ( 10^n - 1 ) = 0 ( mod ( 9 * L / gcd( L, 8 ) ) )
-------> 10^n = 1 ( mod( 9 * L / gcd( L, 8 ) ) )
设 m = 9 * L / gcd( L, 8 )
根据欧拉定理：( 10, m ) != 1 时 方程无解
当 ( 10, m ) == 1 是 phi( m ) 必然是一个解，但是不一定是最小的，故可以从小到大枚举 phi( m ) 的所有因数
pku_3696
1
#include <cstdio>
2#include <iostream>
3#include <cmath>
4#include <algorithm>
5#include <cstring>
6#include <string>
7#include <complex>
8#include <queue>
9using namespace std;
10
11typedef __int64 ll;
12const int maxn = 100006;
13
14int vis[ maxn ], p[ maxn ];
15int plen, flen;
16int a[ 64 ], b[ 64 ];
17
18ll gcd( ll a, ll b ) 
{ return b ? gcd( b, a % b ) : a; }
19
20void prime( )
21{
22
ll i, j, k;
23 plen = 0;
24 memset( vis, 0, sizeof( vis ) );
25 for( i = 2, k = 4; i < maxn; ++i, k += i + i - 1 )
26
{
27 if( !vis[ i ] )
28 {
29 p[ plen++ ] = i;
30 if( k < maxn ) for( j = k; j < maxn; j += i ) vis[ j ] = 1;
31
}
32 }
33
}
34
35ll mul_mod( ll a, ll b, ll c )
36{
37 ll ans = 0, d = a % c;
38 while( b )
39 {
40 if( b & 1 )if( ( ans += d ) >= c ) ans -= c;
41 if( ( d <<= 1 ) >= c ) d -= c;
42 b >>= 1;
43 }
44 return ans ;
45}
46
47ll pow_mod( ll a, ll b, ll c )
48{
49 ll ans = 1, d = a % c;
50 while( b )
51 {
52 if( b & 1 ) ans = mul_mod( ans, d, c );
53 d = mul_mod( d, d, c );
54 b >>= 1;
55 }
56 return ans;
57}
58
59void number_factor( ll n )
60{
61 flen = 1;
62 for( int i = 0; (ll) p[ i ] * p[ i ] <= n; i++ )
63 {
64 if( n % p[ i ] == 0 )
65 {
66 for( b[ flen ] = 0; n % p[ i ] == 0; ++b[ flen ], n /= p[ i ] );
67 a[ flen++ ] = p[ i ];
68 }
69 }
70 if( n > 1 ) a[ flen ] = n, b[ flen++ ] = 1;
71}
72
73ll PHI( ll n )
74{
75 ll phi = n;
76 for( int i = 0; (ll) p[ i ] * p[ i ] <= n; i++ )
77 {
78 if( n % p[ i ] == 0 )
79 {
80 while( !( n % p[ i ] ) )
81 n /= p[ i ];
82 phi = phi / p[ i ] * ( p[ i ] - 1 );
83 }
84 }
85 if( n > 1 ) phi = phi / n * ( n - 1 );
86 return phi;
87}
88
89ll buf[ maxn ], cnt;
90
91void DFS( int dep, ll tmp )
92{
93 if( dep == flen )
94 {
95 buf[ cnt++ ] = tmp;
96 return;
97 }
98 int temp = 1;
99 for( int i = 0; i <= b[ dep ]; i++ )
100 {
101 DFS( dep + 1, tmp * temp );
102 temp *= a[ dep ];
103 }
104}
105
106int main(int argc, char *argv[])
107{
108 ll L;
109 int k = 1;
110 prime( );
111 while( scanf( "%I64d", &L ) && L )
112 {
113 ll m = 9 * L / gcd( L, 8 );
114 if( gcd( 10, m ) != 1 )
115 {
116 printf( "Case %d: 0\n", k++ );
117 continue;
118 }
119 number_factor( PHI( m ) );
120 cnt = 0;
121 DFS( 0, 1 );
122 sort( buf, buf + cnt );
123 ll ans = 0;
124 for( int i = 0; i < cnt; i++ )
125 {
126 if( pow_mod( 10, buf[ i ], m ) == 1 )
127 {
128 ans = buf[ i ];
129 break;
130 }
131 }
132 printf( "Case %d: %I64d\n", k++, ans );
133 }
134 return 0;
135}
136