coreBugZJ

此 blog 已棄。

POJ 3604 Professor Ben

/*
2

POJ 3604 Professor Ben
3

----問(wèn)題描述：
6

Professor Ben is an old stubborn man teaching mathematics in a university. He likes to puzzle his students with perplexing (sometimes boring) problems. Today his task is: for a given integer N, a1,a2,

,an are the factors of N, let bi be the number of factors of ai, your job is to find the sum of cubes of all bi. Looking at the confused faces of his students, Prof. Ben explains it with a satisfied smile:
8

Let's assume N = 4. Then it has three factors 1, 2, and 4. Their numbers of factors are 1, 2 and 3 respectively. So the sum is 1 plus 8 plus 27 which equals 36. So 36 is the answer for N = 4.
10

Given an integer N, your task is to find the answer.
12

----輸入：
15

The first line contains the number the test cases, Q(1 ≤ Q ≤ 500000). Each test case contains an integer N(1 ≤ N ≤ 5000000)
17

----輸出：
20

For each test case output the answer in a separate line.
22

----樣例輸入：
25

1
27

4
28

----樣例輸出：
31

36
33

----分析：
36

由算術(shù)基本定理，
38

設(shè) N 有 k 個(gè)質(zhì)因子 P1, P2,

. , Pk
40

則
41

N = P1^A1 + P2^A2 +

. + Pk^Ak
42

設(shè) N 有 m 個(gè)因子 F1, F2,

. , Fm
44

則
45

Fj = P1^B1j + P2^B2j +

. + Pk^Bkj (0 <= Bij <= Ai)
46

對(duì)任意 Fx 和 Fy，當(dāng) x != y 時(shí)，必存在 r 使 Brx != Bry
47

則 Fj 的因子數(shù)
49

Sj = (1+B1j) * (1+B2j) *

. * (1+Bkj)
50

則最終結(jié)果
52

ANS = S1^3 + S2^3 +

. + Sm^3
53

= (1+B11)^3 * (1+B21)^3 *

. * (1+Bk1)^3 +
54

(1+B12)^3 * (1+B22)^3 *

. * (1+Bk2)^3 +
55

. +
56

(1+B1m)^3 * (1+B2m)^3 *

. * (1+Bkm)^3
57

其中 Bxy = 0, 1, 2,

. , Ax
58

合并同類項(xiàng)
60

ANS = (1^3 + 2^3 +

. + (1+A1)^3) *
61

(1^3 + 2^3 +

. + (1+A2)^3) *
62

. *
63

(1^3 + 2^3 +

. + (1+Ak)^3)
64

*/
66

/**********************************************
69

版本二：
70

*/
72

#include <iostream>
74

#include <cstdio>
75

#include <cstring>
76

using namespace std;
78

typedef __int64 Lint;
80

#define N 5000009
82

#define RN 2240
83

int nprime, prime[ RN ];
85

void init() {
87

int i, j;
88

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

nprime = 0;
90

for ( i = 2; i < RN; ++i ) {
91

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

prime[ nprime++ ] = i;
93

for ( j = i + i; j < RN; j += i ) {
94

prime[ j ] = 1;
95

}
96

}
97

}
98

}
99

100

// calc 1^3 + 2^3 +

. + (1+a)^3
101

Lint sum( int a ) {
102

Lint n = a + 1;
103

Lint h = ( (n&1) ? ((n+1)/2*n) : (n/2*(n+1)) );
104

return h * h;
105

}
106

107

Lint solve( int n ) {
108

int i = -1, p, a;
109

Lint ans = 1;
110

while ( 1 != n ) {
111

do {
112

++i;
113

} while ( (i < nprime) && (n % prime[ i ] != 0) );
114

if ( i >= nprime ) {
115

// n 是質(zhì)數(shù)
116

a = 1;
117

n = 1;
118

}
119

else {
120

a = 0;
121

p = prime[ i ];
122

do {
123

++a;
124

n /= p;
125

} while ( n % p == 0 );
126

}
127

ans *= sum( a );
128

}
129

return ans;
130

}
131

132

int main() {
133

int td, n;
134

init();
135

scanf( "%d", &td );
136

while ( 0 < td-- ) {
137

scanf( "%d", &n );
138

printf( "%I64d\n", solve(n) );
139

}
140

return 0;
141

}
142

143

144

145

/**********************************************
146

版本一：
147

TLE
148

*/
149

/*
150

#include <iostream>
151

#include <cstdio>
152

153

using namespace std;
154

155

typedef __int64 Lint;
156

157

#define N 5000009
158

#define RN 2240
159

160

void init() {
161

}
162

163

// calc 1^3 + 2^3 +

. + (1+a)^3
164

Lint sum( int a ) {
165

Lint n = a + 1;
166

Lint h = ( (n&1) ? ((n+1)/2*n) : (n/2*(n+1)) );
167

return h * h;
168

}
169

170

Lint solve( int n ) {
171

int p = 1, a;
172

Lint ans = 1;
173

while ( 1 != n ) {
174

do {
175

++p;
176

} while ( (p < RN) && (n % p != 0) );
177

if ( RN <= p ) {
178

// n 是質(zhì)數(shù)
179

a = 1;
180

n = 1;
181

}
182

else {
183

a = 0;
184

do {
185

++a;
186

n /= p;
187

} while ( n % p == 0 );
188

}
189

ans *= sum( a );
190

}
191

return ans;
192

}
193

194

int main() {
195

int td, n;
196

init();
197

scanf( "%d", &td );
198

while ( 0 < td-- ) {
199

scanf( "%d", &n );
200

printf( "%I64d\n", solve(n) );
201

}
202

return 0;
203

}
204

*/
205

posted on 2012-06-01 21:30 coreBugZJ 閱讀(1758) 評(píng)論(1) 編輯收藏引用所屬分類: ACM 、Algorithm 、Mathematics 、課內(nèi)作業(yè)

Feedback

# re: POJ 3604 Professor Ben 2014-02-02 12:18 kkkwjx

N = P1^A1 + P2^A2 + . + Pk^Ak
這里為什么是相加而不是相乘？回復(fù) 更多評(píng)論

刷新評(píng)論列表

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


相關(guān)文章: 微軟2014實(shí)習(xí)生及秋令營(yíng)技術(shù)類職位在線測(cè)試 TopCoder SRM 593 DIV2 第三題生成全排列的非回溯方法（TopCoder SRM 591 DIV 2） A* 算法求解八數(shù)碼問(wèn)題，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 博問(wèn) Chat2DB 管理

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

coreBugZJ

My Links

Blog Stats

常用鏈接

留言簿(10)

隨筆分類(458)

隨筆檔案(268)

相冊(cè)

ACM

AI

LaTeX

安全

編程語(yǔ)言

好有道理

技術(shù)

開(kāi)源

科學(xué)

數(shù)學(xué)

圖形圖像

文化

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

資源

最新隨筆

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

POJ 3604 Professor Ben

Feedback

# re: POJ 3604 Professor Ben 2014-02-02 12:18 kkkwjx