「PE#193」Squarefree Numbers - 莫比乌斯函数 + 容斥

PE 氵题 Link: Problem 193 - Project Euler

简要题意

2 ^ {50} 以内无平方因子的数的个数

Squarefree Numbers

A positive integer n is called squarefree, if no square of a prime divides n , thus 1, 2, 3, 5, 6, 7, 10, 11 are squarefree, but not 4, 8, 9, 12 .

How many squarefree numbers are there below 2^{50} ?


题解

注意到 \mu 函数的性质, 当且仅当 \mu(x) = 0 时, 表示 x 有平方因子. 所以问题就是在求

\sum _ {i = 1} ^ n |\mu(i)|

考虑通过枚举质数平方因子容斥, 首先计算质数作为平方因子的, 再计算两质数乘积的, 再计算三质数乘积的...然后容斥就好了, 容斥系数其实就是 \mu

\sum _ {i = 1} ^ n |\mu(i)|=\sum _ { i = 1 } ^ \sqrt n \mu (i) \left \lfloor {n \over i ^ 2} \right \rfloor

然后得到了一个 O(\sqrt n) 的做法, 可以通过本题(雾


代码:

大概跑了 1.4s (

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>

#define int long long

const int N = 1 << 25 | 1 << 3;

int cnt;
int pri[N];
int mu[N];
bool vis[N + 10];

void pre () {
mu[1] = 1;
for (int i = 2; i <= N; i++) {
if (!vis[i]) pri[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && i * pri[j] <= N; j++) {
vis[i * pri[j]] = 1;
if (i % pri[j] == 0) break;
mu[i * pri[j]] = -mu[i];
}
}
}

signed main () {
pre();
int n = 1ll << 50;
int ans = 0;
for (int i = 1ll; i * i <= n; i++) ans += mu[i] * (n / (i * i));
printf("%lld\n", ans);
return 0;
}
坚持原创技术分享,您的支持将鼓励我继续创作!