洛谷p2568 Gcd（莫比烏斯反演）

題目連結

p2568

解體思路

直接進行莫比烏斯反演

過程如下

我們枚舉d，把 μ \mu μ求一個字首和，然後通過分塊來做這道題，不分塊我不知道能不能過。

AC代碼

#include <iostream>

using namespace std;
const int MAX_N = 1e7+8;

int vis[MAX_N], prime[MAX_N], mu[MAX_N];
long long f[MAX_N];
int ans = 0;

void init(int n)
{
    mu[1] = 1;

    for (int i=2; i<=n; i++)
    {
        if (!vis[i])
        {
            prime[ans++] = i;
            mu[i] = -1;
        }

        for (int j=0; j<ans && i*prime[j] <= n; j++)
        {
            vis[i*prime[j]] = 1;

            if (i%prime[j])
            {
                mu[i*prime[j]] = -mu[i];
            }
            else
            {
                mu[i*prime[j]] = 0;
                break;
            }
        }

        mu[i] += mu[i-1];
    }
}

int main()
{
    long long n;
    long long sum = 0;

    scanf("%lld", &n);

    init(n);

    for (int i=0; i<ans; i++)
    {
        long long m=n/prime[i];
        for (long long l=1, r; l<=m; l=r+1)
        {
            r = min(m/(m/l), m);
            sum+=(m/l)*(m/l)*(mu[r]-mu[l-1]);
        }
    }

    printf("%lld\n", sum);

    return 0;
}