记录编号	322089	评测结果	AAAAAAAAAA
题目名称	[UVa 11426] 最大公约数之和——极限版II	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	13.555 s
提交时间	2016-10-14 17:45:48	内存使用	62.28 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <list>
#include <queue>
#include <vector>
#include <map>
#include <numeric>
using namespace std;
#define MAXN 5000001
typedef long long LL;
bool vis[MAXN];
LL phi[MAXN];
int prime[MAXN];
int totp;
void pre(LL maxn)
{
    phi[0] = 0;
    phi[1] = 1;
    for(int i = 2; i <= maxn; i++)
    {
        if(!vis[i])
        {
            prime[totp++] = i;
            phi[i] = i-1;
        }
        for(int j = 0; j < totp && i*prime[j] <= maxn; j++)
        {
            int k = i*prime[j];
            vis[k] = true;
            if(i%prime[j])
            {
                phi[k] = phi[i]*(prime[j]-1);
            }else
            {
                phi[k] = phi[i]*prime[j];
                break;
            }
        }
    }
    for(int i = 1; i <= maxn; i++)
        phi[i] += phi[i-1];
}
int main()
{
    freopen("gcd_extreme.in", "r", stdin);
    freopen("gcd_extreme.out", "w", stdout);
    pre(MAXN);
    while(true)
    {
        int n;
        long long s = 0;
        scanf("%d", &n);
        if(!n)break;
        for(int i = 1; i <= n; i++)
            s += i*(phi[n/i]-1);
        printf("%lld\n", s);
    }
    return 0;
}