悬关 莫比乌斯反演 95pts 求调

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e7+7,mod=20101009;
int n,m,mu[N],prime[N],top,f[N],ans;
bool vis[N];

int tot(int x){
	return (x*(x+1)/2)%mod;
}

void init(){
	mu[1]=1;
	for(int i=2;i<N;++i){
		if(!vis[i]){
			mu[i]=-1;
			prime[++top]=i;
		}
		for(int j=1;j<=top,i*prime[j]<N;++j){
			vis[i*prime[j]]=true;
			if(i%prime[j]==0){
				mu[i*prime[j]]=0;
				break;
			}
			mu[i*prime[j]]=-mu[i];
		}
	}
	for(int t=1;t<N;++t)
		f[t]=((t%mod*t%mod)%mod*mu[t])%mod;
	for(int i=1;i<N;++i)
		f[i]=(f[i]+f[i-1]%mod)%mod;
}

int compute(int n,int m,int d){
	n/=d,m/=d;
	int res=0;
	for(int l=1,r;l<=n;l=r+1){
		r=min(n/(n/l),m/(m/l));
		res+=((((f[r]-f[l-1])%mod*tot(n/l))%mod)*(tot(m/l)%mod))%mod;
	}
	return res%mod;
}

signed main(){
	init();
	cin>>n>>m;
	if(n>m)
		swap(n,m);
	for(int d=1;d<=n;++d)
		ans+=(d*compute(n,m,d)%mod)%mod;
	cout<<ans%mod;
	return 0;
}