ACM模版

描述

题解

题目要求所有小于等于 N 的两两之间的最大公约数的和，如果我们直接这么考虑两者之间的关系其实并不好想，我们可以先固定一个来考虑。如果我们求 [1,n] 与 m 的 GCD 的和是多少呢？

设 GCD(m,i)==x ，那么我们很容易就能得到 GCD(m/x,i/x)==1 ，所以顺理成章可以确定的是，这个结果就是 [1,i/x] 区间与 i/x 互素的个数有多少，也就是欧拉函数，然后再乘以我们除去的这个 x ，毕竟我们将原本的结果缩小了 x 倍，再乘回来理所当然。所以最后他的结果也就是：

∑i=1,i|nnphi(n/i)∗i
。

最后，回到本来的问题：

G=∑i=1N−1∑j=i+1NGCD(i,j)=∑i=2N∑j=1i−1GCD(i,j)=∑i=2N∑j=1,j|ii−1phi(i/j)∗j=∑i=1N∑j=2,i∗j≤NNi∗phi(j)

所以呢，最后就变成了一个预处理获取 phi() 的问题，这里用线性筛处理比较好，可以在合适的时间内 AC ……具体的请看代码吧，十分清晰，没什么难理解的地方。

代码

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long ll;

const int MAXN = 5e6 + 50;

int N;
ll ans[MAXN];
int prime[MAXN];
int phi[MAXN];
bool flag[MAXN];

void get_phi()
{
    int cnt = 0;
    memset(flag, true, sizeof(flag));

    phi[1] = 1;
    for(int i = 2; i < MAXN; i++)
    {
        if (flag[i])
        {
            prime[cnt++] = i;
            phi[i] = i - 1;
        }
        for (int j = 0; j < cnt; j++)
        {
            if (1ll * i * prime[j] > MAXN)
            {
                break;
            }
            flag[i * prime[j]] = false;
            if (i % prime[j] == 0)
            {
                phi[i * prime[j]] = prime[j] * phi[i];
                break;
            }
            else
            {
                phi[i * prime[j]] = (prime[j] - 1) * phi[i];
            }
        }
    }
}

void init()
{
    get_phi();
    memset(ans, 0, sizeof(ans));

    for (int i = 1; i < MAXN; i++)
    {
        for (int j = 2; j < MAXN; j++)
        {
            if (1ll * i * j < MAXN)
            {
                ans[1ll * i * j] += phi[j] * i;
            }
            else
            {
                break;
            }
        }
    }

    for (int i = 1; i < MAXN; i++)
    {
        ans[i] += ans[i - 1];
    }
}

template <class T>
inline void scan_d(T &ret)
{
    char c;
    ret = 0;
    while ((c = getchar()) < '0' || c > '9');
    while (c >= '0' && c <= '9')
    {
        ret = ret * 10 + (c - '0'), c = getchar();
    }
}

template <class T>
inline void print_d(T x)
{
    if (x > 9)
    {
        print_d(x / 10);
    }
    putchar(x % 10 + '0');
}

int main()
{
    init();

    int T;
    scan_d(T);
    while (T--)
    {
        scan_d(N);
        print_d(ans[N]);
        putchar(10);
    }

    return 0;
}