UVA-11426(欧拉函数)

题目VJ链接:https://vjudge.net/problem/UVA-11426

题目大意:

求这个

G=0;
for(i=1;i<N;i++)
for(j=i+1;j<=N;j++)
{
	G+=gcd(i,j);
}

\(1<N<4000001\)

思路:

这是一个计算贡献的题,首先考虑两个数\(a,b\)互质，那么\(GCD\left( a,b\right)=1 \),\(GCD\left( 2a,2b\right)=2 \),以此类推即可求出答案。
首先打欧拉函数表算出与\(x\)互质的数的个数，然后\(x*2\)这样推下去，详见代码.

AC代码

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
#define wfor(i,j,k) for(i=j;i<k;++i)
#define mfor(i,j,k) for(i=j;i>=k;--i)
// void read(int &x) {
//  char ch = getchar(); x = 0;
//  for (; ch < '0' || ch > '9'; ch = getchar());
//  for (; ch >= '0' && ch <= '9'; ch = getchar()) x = x * 10 + ch - '0';
// }
const int maxn = 4e6 + 2;
int eul[maxn];
void get_eul()
{
    eul[1] = 0;
    int i;
    wfor(i, 2, maxn)
    eul[i] = i;
    wfor(i, 2, maxn)
    {
        if (eul[i] == i)
        {
            int j;
            for (j = i; j < maxn; j += i)
                eul[j] = eul[j] / i * (i - 1);
        }
    }
}
ll ans[maxn];//ans[i]里储存的是i的贡献
ll sum[maxn];
int main()
{
    std::ios::sync_with_stdio(false);
#ifdef test
    freopen("F:\\Desktop\\question\\in.txt", "r", stdin);
#endif
#ifdef ubuntu
    freopen("/home/time/debug/debug/in", "r", stdin);
    freopen("/home/time/debug/debug/out", "w", stdout);
#endif
    int n;
    ll i, j;
    get_eul();
    wfor(i, 1, maxn)
    {
        for (j = 2 * i; j < maxn; j += i)
        {
            ans[j] += eul[j / i] * i;//是几倍，gcd就是几
        }
    }
    wfor(i, 2, maxn)
    {
        sum[i] = sum[i - 1] + ans[i];//预处理所有答案
    }
    while (cin >> n && n)
    {
        cout << sum[n] << endl;
    }
    return 0;
}