51Nod-1594-Gcd and Phi

描述

题解

这个题更准确的描述应该是求

F (n) = \sum i = 1 n \sum j = 1 n ϕ g c d (ϕ i, ϕ j)

首先我们可以设

s[i] 表示

1∼n 中欧拉函数等于

i 的数有多少个。那么我们可以得到：

F (n) = \sum d = 1 n \sum i = 1 ⌊ n d ⌋ \sum j = 1 ⌊ n d ⌋ ϕ d * s [i d] * s [j d] [g c d (i, j) = 1]

此时，反演可以上了。

设

g (d) = \sum i = 1 ⌊ n d ⌋ \sum j = 1 ⌊ n d ⌋ s [i d] * s [j d] [g c d (i, j) = 1]

f (d) = \sum k = 1 ⌊ n d ⌋ g (k d)

所以

f (d) = \sum i = 1 ⌊ n d ⌋ \sum j = 1 ⌊ n d ⌋ s [i d] * s [j d]

这里的

f 数组预处理一下即可。

所以由于

g (d) = \sum i = 1 ⌊ n d ⌋ μ i * f (i d)

所以

F (n) = \sum d = 1 n g (d) * ϕ d = \sum d = 1 n ϕ d \sum i = 1 ⌊ n d ⌋ μ i * f (i d)

如此这般，套模版就好了。

代码

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 2e6 + 5;

int n, tot;
ll ans;
ll s[MAXN];
ll f[MAXN];
int pri[MAXN];
int phi[MAXN];
int miu[MAXN];
bool vis[MAXN];

void solve()
{
    memset(vis, 0, sizeof(vis));
    memset(phi, 0, sizeof(phi));
    memset(miu, 0, sizeof(miu));
    memset(s, 0, sizeof(s));
    memset(f, 0, sizeof(f));
    ans = tot = 0;
    miu[1] = phi[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        if (!vis[i])
        {
            pri[tot++] =i ;
            miu[i] = -1;
            phi[i] = i - 1;
        }
        for (int j = 0, k; j < tot; j++)
        {
            k = i * pri[j];
            if (k > n)
            {
                break;
            }

            vis[k] = 1;
            if (i % pri[j] == 0)
            {
                miu[k] = 0;
                phi[k] = phi[i] * pri[j];
                break;
            }

            miu[k] = -miu[i];
            phi[k] = phi[i] * (pri[j] - 1);
        }
    }

    for (int i = 1; i <= n; i++)
    {
        s[phi[i]]++;
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = i; j <= n; j += i)
        {
            f[i] += s[j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        f[i] = f[i] * f[i];
    }
    for (int i = 1; i <= n; i++)
    {
        if (miu[i] != 0)
        {
            for (int d = 1; i * d <= n; d++)
            {
                ans += miu[i] * phi[d] * f[i * d];
            }
        }
    }
}

int main()
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        scanf("%d", &n);

        solve();

        printf("%lld\n", ans);
    }

    return 0;
}