BZOJ-2005: [Noi2010]能量采集

Description

求

感觉是时候复习一下了。。。
这道题我居然不会。。。
不妨设n<=m
因为原式等于将d提到前面，发现d被统计的次数即为n/d*m/d
原式即为

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
long long n,m;
int phi[101000],prime[101000],cnt;
bool v[101000];
long long ans;
void quick_euler()
{
    phi[1]=1;
    for(int i=2;i<=100001;i++)
    {
        if(!v[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=100001;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    scanf("%lld%lld",&n,&m);
    if(n>m)
        swap(n,m);
    quick_euler();
    for(int i=1;i<=n;i++)
        ans+=phi[i]*(n/i)*(m/i);
    printf("%lld",ans*2-n*m);
    return 0;
}