记录编号	587470	评测结果	AAAAAAAAAA
题目名称	[NOI 2010]能量采集	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2024-04-01 16:57:25	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
//莫比乌斯反演 
#define ll long long
const int N = 1e5+10;
const ll inf = 1e17;
int n,m;
int p[N],low[N],cnt;
ll f[N];
bool v[N];
void get(){
    f[1] = 1;
    for(int i = 2;i <= 1e5;i++){
        if(!v[i])low[i] = p[++cnt] = i,f[i] = i - 1;
        for(int j = 1;j <= cnt && i <= 1e5 / p[j];j++){
            int t = i * p[j];v[t] = 1;
            if(i % p[j] == 0){
                low[t] = low[i] * p[j];
                if(low[i] == i)f[t] = (ll)t - i;
                else f[t] = f[i/low[i]] * f[low[t]];break;
            }
            low[t] = p[j],f[t] = f[i] * f[p[j]];
        }
    }
    for(int i = 1;i <= 1e5;i++)f[i] += f[i-1];
}
int main(){
	freopen("energy2010.in","r",stdin);
    freopen("energy2010.out","w",stdout);
    get();
    scanf("%d%d",&n,&m);
    if(n > m)swap(n,m);
    ll ans = 0;
    for(int l = 1,r;l <= n;l = r + 1){
        r = min(n,min(n / (n / l),m / (m / l)));
        ans += 1ll * (n / l) * (m / l) * (f[r] - f[l-1]);
    }
    printf("%lld\n",2 * ans - 1ll * n * m);
	return 0;
 
}