【翻转硬币——莫比乌斯函数、分块、卷积、埃氏筛】

题目

暴力代码，官网过55%

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int n;
    cin >> n;
    vector<bool> a(n + 1);

    a[1] = 1;
    int res = 1;
    for (int i = 2; i <= n; i++)
    {
        if (a[i] == 0)
        {
            for (int j = i; j <= n; j += i)
                a[j] = a[j] ^ 1;
            res++;
        }
    }

    cout << res;
}

代码

#include <iostream>
#include <unordered_map>
#include <cmath>
using namespace std;
using ll = long long;
const int N = 20000010;
int primes[N], cnt;
bool st[N];
int mu[N];
unordered_map<int, int> mp;

void init(int n)
{
    mu[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!st[i])
        {
            primes[cnt++] = i;
            mu[i] = -1;
        }
        for (int j = 0; j < cnt && primes[j] * i <= n; j++)
        {
            int x = primes[j];
            st[i * x] = true;
            if (i % x == 0)
            {
                break;
            }
            else
            {
                mu[i * x] = -mu[i]; // 利用积性 mu[i*x] = mu[x] * mu[i]，其中mu[x] = -1
            }
        }
    }
    for (int i = 1; i <= n; i++) // 求莫比乌斯函数的前缀和（<=2e7）
        mu[i] += mu[i - 1];
}

int cal(int n) // 记忆化计算莫比乌斯函数的前缀和（>2e7）
{
    if (n <= 20000000)
        return mu[n];
    if (mp.count(n))
        return mp[n];
    ll res = 1;
    for (ll l = 2, r; l <= n; l = r + 1) // 杜教筛（不太懂QAQ）
    {
        r = n / (n / l);
        res -= (r - l + 1) * cal(n / l);
    }
    return mp[n] = res;
}

int main()
{
    init(20000000);
    ll n;
    cin >> n;
    ll res = 0;
    for (ll l = 1, r; l <= n / l; l = r + 1) // 公式1简化+分块，注意权重形式是n/i/i
    {
        r = sqrt(n / (n / l / l));
        res += (cal(r) - cal(l - 1)) * (n / (l * l));
    }
    cout << res << '\n';
    return 0;
}