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

（轉(zhuǎn)自網(wǎng)上）
40

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

解題思路：因?yàn)镸全部由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互質(zhì)，則(10^x-1)%q==0;
50

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

根據(jù)歐拉定理可知當(dāng)gcd(a,b)==1時(shí)，a^φ(b)≡1(mod b);
54

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

由于N比較大，因此采用long long 型。同時(shí)做一個(gè)素?cái)?shù)表。
58

在進(jìn)行冪求模運(yùn)算的時(shí)候可以采用快速冪的方法。
60

由于在進(jìn)行快速冪求模的時(shí)候數(shù)據(jù)會(huì)超出long long 的表示范圍，因此要進(jìn)行優(yōu)化。
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) 評(píng)論(0) 編輯收藏引用所屬分類: ACM 、Algorithm 、Mathematics 、課內(nèi)作業(yè)

只有注冊(cè)用戶登錄后才能發(fā)表評(píng)論。


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

網(wǎng)站導(dǎo)航: 博客園 IT新聞 BlogJava 博問 Chat2DB 管理

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊(cè)

ACM

AI

LaTeX

安全

編程語言

好有道理

技術(shù)

開源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

問題（練習(xí)＆有趣）

資源

最新隨筆

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

POJ 3696 The Luckiest number