題目：將
n
n
n分解為
a
?
b
a*b
a?b的形式，且
a
a
a和
b
b
b均為無平方因子，
f
(
n
)
f(n)
f(n)可分解的總方式，例如：
6
=
1
?
6
=
6
?
1
=
2
?
3
=
3
?
2
6=1*6=6*1=2*3=3*2
6=1?6=6?1=2?3=3?2，因此
f
(
6
)
=
4
f(6)=4
f(6)=4，
求
∑
i
=
1
n
f
(
i
)
\sum_{i=1}^nf(i)
∑i=1n?f(i)
分析：唯一分解定理、歐拉篩
令
n
=
i
?
p
[
j
]
n=i*p[j]
n=i?p[j]
如果
i
i
i%
(
p
[
j
]
)
2
=
0
(p[j])^2=0
(p[j])2=0,則
i
=
k
?
(
p
[
j
]
)
2
i=k*(p[j])^2
i=k?(p[j])2,則
n
=
k
?
(
p
[
j
]
)
3
n=k*(p[j])^3
n=k?(p[j])3,所以
f
(
n
)
=
0
f(n)=0
f(n)=0
如果
i
i
i%
(
p
[
j
]
)
=
0
(p[j])=0
(p[j])=0,則
i
=
k
?
(
p
[
j
]
)
i=k*(p[j])
i=k?(p[j]),則
n
=
k
?
(
p
[
j
]
)
2
n=k*(p[j])^2
n=k?(p[j])2,所以
f
(
n
)
=
f
(
k
)
=
f
(
i
/
p
[
j
]
)
f(n)=f(k)=f(i/p[j])
f(n)=f(k)=f(i/p[j])
如果
i
i
i%
(
p
[
j
]
)
!
=
0
(p[j])!=0
(p[j])!=0,所以
f
(
n
)
=
f
(
i
)
?
2
f(n)=f(i)*2
f(n)=f(i)?2
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
const int MAXN = 20000005;
int p[MAXN], f[MAXN];
void getf() {
memset(p, 0, sizeof(p));
f[1] = 1;
for (int i = 2; i <= MAXN; i++) {
if (!p[i]) {
p[++p[0]] = i;
f[i] = 2;
}
for (int j = 1; j <= p[0] && p[j] <= MAXN / i; j++) {
p[i * p[j]] = 1;
if (i % (p[j] * p[j]) == 0)
f[i * p[j]] = 0;
else if (i % p[j] == 0) {
f[i * p[j]] = f[i / p[j]];
break;
}
else
f[i * p[j]] = f[i] * 2;
}
}
}
int main() {
IOS;
getf();
int t;
cin >> t;
while (t--) {
int n;
cin >> n;
int count = 0;
for (int i = 1; i <= n; i++)
count += f[i];
cout << count << endl;
}
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/yidong/261752.html
標籤：其他