我做这题的经历告诉了我：不要乱取模
多取了一个mod 然后WA无数次
我这个方法并不是最优的
懒得写题解了
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
const long long Mod=20101009ll;
int mu[10000005],pri[10000005],cnt,tab[10000005];
long long n,m,ans,s[10000005],Mn;
long long Sum(long long x,long long y){return ((x*(x+1)/2)%Mod)*((y*(y+1)/2)%Mod)%Mod;}
void Prepare(){
mu[1]=1;
Mn=min(n,m);
for(long long i=2;i<=Mn;i++){
if(!tab[i]){pri[++cnt]=i;mu[i]=-1;}
for(long long j=1;j<=cnt && i*pri[j]<=Mn;j++){
tab[i*pri[j]]=1;
if(i%pri[j]){mu[i*pri[j]]=-mu[i];}
else {mu[i*pri[j]]=0;break;}
}
}
for(long long i=1;i<=Mn;i++)s[i]=(s[i-1]+(i*i*mu[i])%Mod)%Mod;
}
long long F(long long x,long long y){
long long j,ans=0,Mn2=min(x,y);
for(long long i=1;i<=Mn2;i=j+1){
j=min(x/(x/i),y/(y/i));
ans=(ans+(s[j]-s[i-1])*Sum(x/i,y/i)%Mod)%Mod;
}
return ans;
}
int main(){
freopen("2154.in","r",stdin);
freopen("2154.out","w",stdout);
scanf("%lld %lld",&n,&m);
Prepare();
long long j;
for(long long i=1;i<=Mn;i=j+1){
j=min(n/(n/i),m/(m/i));
ans=(ans+(j+i)*(j-i+1)/2%Mod*F(n/i,m/i)%Mod)%Mod;
}
printf("%lld\n",(ans+Mod)%Mod);
return 0;
}
评论 (0)
