Crash的数学题

#include<bits/stdc++.h>
using namespace std;
const int N=1e7+5,mod=20101009;
bool NotPrime[N];
int tot;
int Prime[N],f[N];
long long pre[N];
void sieve(int n){
	NotPrime[1]=1;
	f[1]=1;
	for(int i=2;i<=n;i++){
		if(!NotPrime[i]){
			Prime[tot++]=i;
			f[i]=1-i;
		}
		for(int j=0,k;(k=i*Prime[j])<=n;j++){
			NotPrime[k]=1;
			if(i%Prime[j]==0){
				f[k]=f[i];
				break;
			}
			f[k]=f[i]*f[Prime[j]];
		}
	}
	for(int i=1;i<=n;i++){
		pre[i]=(pre[i-1]+(long long)f[i]*i%mod+mod)%mod;
	}
} 
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	if(n>m)swap(n,m);
	sieve(n);
	long long ans=0;
	for(int i=1,j;i<=n;i=j+1){
		j=min(n/(n/i),m/(m/i));
		long long s1=(long long)(1+n/i)*(n/i)/2%mod,s2=(long long)(1+m/i)*(m/i)/2%mod;
		ans+=s1%mod*s2%mod*(pre[j]-pre[i-1]+mod)%mod;
		ans%=mod;
	}
	printf("%lld\n",ans);
	return 0;
}

线性筛原理解释：
题目原始式子是\(\sum_{i=1}^n\)
P1829

Crash的数学题

原文：https://www.cnblogs.com/-9-QAQ-6-/p/13045559.html