TIOJ-1600

2qbingxuan

2020-01-26

TIOJ , math

爆炸吧現充~

https://tioj.ck.tp.edu.tw/problems/1600

Description

求共有幾個滿足

$$
1 \leq x \leq n,
\exists k > 1, k^2 | x
$$

的$x$

Solution

一開始我的想法是$[\mu(x)=0]$的前綴，想說用杜教篩或莫比烏斯反演什麼的，但怎麼推都推不出來
去問王政祺之後，他說直接枚舉平方數再排容就好，至於排容的係數就直接取$\mu$

令

$$
S_k = \{x | 1 \leq x = k^2t \leq n\}
$$

則答案就是

$$
\begin{matrix}
|\bigcup _ {k} S_k| &= & (|S_2| + |S_3| + |S_5| + |S_7| + \cdots)\newline
&- & (|S_6|+|S _ {10}|+|S _ {14}|+|S _ {15}|+ \cdots)\newline
&+ & (|S _ {30}|+|S _ {42}|+|S _ {66}|+|S _ {70}|+ \cdots)\newline
& & \vdots\newline
&= & \sum -\mu(k) |S_k|\newline
&= & -\sum\limits _ {k=2}^\sqrt{n} \mu(k) \frac{n}{k^2}
\end{matrix}
$$

依照不同質因數去分類，可以發現排容的正負號和$\mu$一致(我也不太會證明最後的部分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';
    }
}