我们要求的是∑ni=1∑mj=1(2×gcd(i,j)−1)

化简得2×∑ni=1∑mj=1gcd(i,j)−n×m

所以我们现在只需要求出∑ni=1∑mj=1gcd(i,j)即可

∑ni=1∑mj=1gcd(i,j)

=∑ni=1∑mj=1∑d|gcd(i,j)ϕ(d)

=∑min(n,m)d=1ϕ(d)×⌊nd⌋×⌊md⌋

预处理ϕ的前缀和，下底分组即可

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<ctime>

#define N 100500

using namespace std;

int prime[N],tot,n,m;

long long phi[N],ans;

bool bo[N];

void init(){

    phi[1]=1;

    for(int i=2;i<=n;i++){

        if(!bo[i]){

            prime[++tot]=i;

            phi[i]=i-1;

        }

        for(int j=1;j<=tot&&i*prime[j]<=n;j++){

            bo[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);

        }

    }

    for(int i=1;i<=n;i++)phi[i]+=phi[i-1];

}

int main(){

    scanf("%d%d",&n,&m);

    if(n>m)swap(n,m);

    init();

    for(int i=1,j;i<=n;i=j+1){

        j=min(n/(n/i),m/(m/i));

        ans+=(long long)(phi[j]-phi[i-1])*(n/i)*(m/i);

    }

    ans*=2; ans-=(long long)n*m;

    printf("%lld\n",ans);

    return 0;

}