coreBugZJ

此 blog 已棄。

POJ 3696 The Luckiest number

/*
2

POJ 3696 The Luckiest number
3

----問題描述：
6

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'.
8

----輸入：
11

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

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

----輸出：
18

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.
20

----樣例輸入：
23

8
25

11
26

16
27

0
28

----樣例輸出：
31

Case 1: 1
33

Case 2: 2
34

Case 3: 0
35

----分析：
38

（轉自網上）
40

題意：給一個數N(1<=N<=2000000000);問是否存在N的倍數M，且M的各個位全部由8組成，如果存在多個取最小的 M 并輸出M由幾個8組成。
42

解題思路：因為M全部由8組成，即M=（10^x -1）*8/9=k*N;
44

則 (10^x-1)*8/gcd(8,N)=9*k*N/gcd(8,N);
46

令p=8/gcd(8,N); q=9*N/gcd(8,N); 即 (10^x-1)*p=k*q;
48

由于p和q互質，則(10^x-1)%q==0;
50

根據同余定理可知，10^x ≡1（mod q）
52

根據歐拉定理可知當gcd(a,b)==1時，a^φ(b)≡1(mod b);
54

即可得出：當gcd(10,q)==1時 10^φ(q)≡1(mod q) 即通過枚舉φ(q)的因子（最小因子）就能得出結果
56

由于N比較大，因此采用long long 型。同時做一個素數表。
58

在進行冪求模運算的時候可以采用快速冪的方法。
60

由于在進行快速冪求模的時候數據會超出long long 的表示范圍，因此要進行優化。
62

*/
65

/**********************************************
68

版本一：
69

*/
70

#include <iostream>
72

#include <cstdio>
73

#include <cstring>
74

using namespace std;
76

typedef __int64 Lint;
78

#define LP 45000
80

int nprime;
81

Lint prime[ LP ];
82

#define LF 128
84

int nf;
85

Lint f[ LF ];
86

void init_prime() {
88

int i, j;
89

nprime = 0;
90

memset( prime, 0, sizeof(prime) );
91

for ( i = 2; i < LP; ++i ) {
92

if ( 0 == prime[ i ] ) {
93

prime[ nprime++ ] = i;
94

for ( j = i+i; j < LP; j += i ) {
95

prime[ j ] = 1;
96

}
97

}
98

}
99

}
100

101

void calc_f( Lint n ) {
102

int i;
103

nf = 0;
104

for ( i = 0; (i < nprime)&&(prime[i]*prime[i] <= n); ++i ) {
105

while ( n % prime[ i ] == 0 ) {
106

f[ nf++ ] = prime[ i ];
107

n /= prime[ i ];
108

}
109

}
110

if ( 1 < n ) {
111

f[ nf++ ] = n;
112

}
113

}
114

115

Lint gcd( Lint a, Lint b ) {
116

Lint t;
117

while ( 0 != b ) {
118

t = a;
119

a = b;
120

b = t % b;
121

}
122

return a;
123

}
124

// a * b % m
125

Lint mul_mod( Lint a, Lint b, Lint m ) {
126

Lint s = 0;
127

a %= m;
128

while ( 0 != b ) {
129

if ( 0 != (1 & b) ) {
130

s += a;
131

if ( s >= m ) {
132

s -= m;
133

}
134

}
135

a <<= 1;
136

if ( a >= m ) {
137

a -= m;
138

}
139

b >>= 1;
140

}
141

return s;
142

}
143

// a ^ b % m
144

Lint pow_mod( Lint a, Lint b, Lint m ) {
145

Lint s = 1;
146

a %= m;
147

while ( 0 != b ) {
148

if ( 0 != (1 & b) ) {
149

s = mul_mod( s, a, m );
150

}
151

a = mul_mod( a, a, m );
152

b >>= 1;
153

}
154

return s;
155

}
156

// 歐拉
157

Lint phi( Lint n ) {
158

Lint s = n;
159

int i;
160

for ( i = 0; (i < nprime)&&(prime[i]*prime[i] <= n); ++i ) {
161

if ( n % prime[ i ] == 0 ) {
162

s = s / prime[ i ] * (prime[ i ] - 1);
163

do {
164

n /= prime[ i ];
165

} while ( n % prime[ i ] == 0 );
166

}
167

}
168

if ( 1 < n ) {
169

s = s / n * (n - 1);
170

}
171

return s;
172

}
173

174

Lint solve( Lint n ) {
175

Lint m = 9 * n / gcd(8, n);
176

if ( 1 != gcd(10, m) ) {
177

return 0;
178

}
179

180

Lint ph = phi(m);
181

Lint s = ph;
182

int i;
183

bool down = true;
184

while ( down ) {
185

down = false;
186

calc_f(ph);
187

for ( i = 0; i < nf; ++i ) {
188

if ( (pow_mod(10, ph/f[i], m) == 1) && (ph/f[i] < s) ) {
189

s = ph / f[ i ];
190

down = true;
191

}
192

}
193

ph = s;
194

}
195

return s;
196

}
197

198

int main() {
199

int td = 0, n;
200

init_prime();
201

while ( (1 == scanf("%d", &n)) && (0 < n) ) {
202

printf( "Case %d: %I64d\n", ++td, solve(n) );
203

}
204

return 0;
205

}
206

posted on 2012-06-01 21:32 coreBugZJ 閱讀(742) 評論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、Mathematics 、課內作業

只有注冊用戶登錄后才能發表評論。


相關文章: 微軟2014實習生及秋令營技術類職位在線測試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數碼問題，POJ 1077 Eight POJ 1067 取石子游戲 POJ 2068 Nim POJ 2975 Nim POJ 3696 The Luckiest number POJ 3604 Professor Ben EOJ 1117 剩余定理

網站導航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊

ACM

AI

LaTeX

安全

編程語言

好有道理

技術

開源

科學

數學

圖形圖像

文化

問題（練習＆有趣）

資源

最新隨筆

搜索

最新評論

閱讀排行榜

評論排行榜

POJ 3696 The Luckiest number