Cptraser/ 十月 29, 2018/ 2018.10/ 0 comments

这里还是上AntiQuality大佬的博客
注意模数非质数。

#include <cstdio>
#include <algorithm>
#define Mod 19940417
#define rev 3323403
using namespace std;
long long N,M,L,R,P,CntN,CntM,Dele;
long long calc(long long x){
    return x*(x+1)%Mod*(2*x+1)%Mod*rev%Mod;
}
int main()
{
    scanf("%lld%lld",&N,&M),P=min(N,M);
    for(L=1,CntN=N*N%Mod;L<=N;)
        R=N/(N/L),CntN=(CntN-(N/L)*((R-L+1)*(L+R)/2%Mod)+Mod)%Mod,L=R+1;
    for(L=1,CntM=M*M%Mod;L<=M;)
        R=M/(M/L),CntM=(CntM-(M/L)*((R-L+1)*(L+R)/2%Mod)+Mod)%Mod,L=R+1;
    for(L=1;L<=P;){
        R=min(N/(N/L),M/(M/L));
        Dele=(Dele+N*M%Mod*(R-L+1)%Mod+(N/L)*(M/L)%Mod*(calc(R)-calc(L-1)+Mod)%Mod-(M*(N/L)+N*(M/L))%Mod*((R-L+1)*(L+R)/2%Mod)+Mod*5)%Mod;
        L=R+1;
    }
    printf("%lld",(CntN*CntM%Mod-Dele+Mod)%Mod);
}
Share this Post

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>
*
*