TIOJ-1600

3 minute read

爆炸吧現充~

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

Description

求共有幾個滿足

1≤x≤n,∃k>1,k2∣x 1 \leq x \leq n, \exists k > 1, k^2 | x

的xx

Solution

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

令

Sk={x∣1≤x=k2t≤n} S_k = \{x | 1 \leq x = k^2t \leq n\}

則答案就是

∣⋃kSk∣=(∣S2∣+∣S3∣+∣S5∣+∣S7∣+⋯ )−(∣S6∣+∣S10∣+∣S14∣+∣S15∣+⋯ )+(∣S30∣+∣S42∣+∣S66∣+∣S70∣+⋯ )⋮=∑−μ(k)∣Sk∣=−∑k=2nμ(k)nk2 \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';
    }
}