传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2154
题解:http://www.cnblogs.com/jianglangcaijin/archive/2013/11/27/3446169.html
Rank里时间分成了200ms-900ms和3000ms+两大波
似乎有更优做法?有待研究
Code:
#include<cstdio> #include<iostream> #include<algorithm> #include<vector> using namespace std; const int maxn=1e7+5; typedef long long LL; int MOD=20101009; int n,m; bool p[maxn]; int prime[maxn]; LL u[maxn]; void init(int maxn){ u[1]=1; for(int i=2;i<maxn;i++){ if(!p[i]){ prime[++prime[0]]=i;u[i]=-1; }for(int j=1;j<=prime[0]&&i*prime[j]<maxn;j++){ p[i*prime[j]]=1; if(i%prime[j]==0){ u[i*prime[j]]=0;break; }else u[i*prime[j]]=-u[i]; } }for(int i=2;i<maxn;i++)u[i]=(u[i-1]+(LL)(i*u[i]%MOD*i))%MOD; } inline LL S(LL n,LL m){ LL ans=0; if(n>m)swap(n,m); for(int i=1,last;i<=n;i=last+1){ last=min(n/(n/i),m/(m/i)); LL Sum=(n/i*(n/i+1)/2%MOD)*(m/i*(m/i+1)/2%MOD)%MOD; ans=(ans+(LL)(u[last]-u[i-1])*Sum%MOD)%MOD; }return ans; } int main(){ cin>>n>>m; LL ans=0; if(n>m)swap(n,m); init(m+1); for(int i=1,last;i<=n;i=last+1){ last=min(n/(n/i),m/(m/i)); ans=(ans+(LL)(i+last)*(last-i+1)/2*(S(n/i,m/i)))%MOD; }while(ans<0)ans+=MOD; cout<<ans%MOD<<endl; return 0; }