爆炸吧現充~
https://tioj.ck.tp.edu.tw/problems/1600
Description
求共有幾個滿足
1≤x≤n,∃k>1,k2∣x的x
Solution
一開始我的想法是[μ(x)=0]的前綴,想說用杜教篩或莫比烏斯反演什麼的,但怎麼推都推不出來
去問王政祺之後,他說直接枚舉平方數再排容就好,至於排容的係數就直接取μ
令
Sk={x∣1≤x=k2t≤n}則答案就是
∣⋃kSk∣=−+==(∣S2∣+∣S3∣+∣S5∣+∣S7∣+⋯)(∣S6∣+∣S10∣+∣S14∣+∣S15∣+⋯)(∣S30∣+∣S42∣+∣S66∣+∣S70∣+⋯)⋮∑−μ(k)∣Sk∣−k=2∑nμ(k)k2n依照不同質因數去分類,可以發現排容的正負號和μ一致(我也不太會證明最後的部分QQ)
看來我的思維要再靈活一些 > <
AC code
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
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll
const ll N = 1000025;
int mu[N],np[N];
vector<int> prs;
signed main() {
mu[1] = np[1] = 1;
for(int i = 2; i < N; i++) {
if(!np[i]) prs.push_back(i), mu[i] = -1;
for(int p: prs) {
if(i*p >= N) break;
np[i*p] = 1;
if(i%p) {
mu[i*p] = -mu[i];
}else {
mu[i*p] = 0;
break;
}
}
}
ll ans = 0, n;
while(cin >> n) {
ans = 0;
for(ll i = 2; i*i <= n; i++) ans -= n / (i*i) * mu[i];
cout << ans << '\n';
}
}
|