BZOJ 2956 模积和

2019-04-13 17:27发布

站内文章 / 模拟电子
10397 0 1221
题目链接：http://61.187.179.132/JudgeOnline/problem.php?id=2956 题意：给出n和m。计算：   思路：  




i64 n,m;


i64 cal(i64 m,i64 n)
{
    i64 ans=0,i,x,y;
    for(i=1;i<=n;i++)
    {
        x=m/i; y=min(n,m/x);
        ans+=(i+y)*(y-i+1)/2%mod*x%mod;
        ans%=mod;
        i=y;
    }
    return ans;
}


i64 get(i64 n)
{
    i64 a=n,b=n+1,c=2*n+1;
    
    if(a%2==0) a>>=1;
    else b>>=1;
    
    if(a%3==0) a/=3;
    else if(b%3==0) b/=3;
    else c/=3;
    
    return a*b%mod*c%mod;
}


i64 cal(i64 n,i64 m,i64 k)
{
    i64 ans=0,i,x,y,z;
    for(i=1;i<=k;i++)
    {
        x=n/i; y=m/i; z=min(k,min(n/x,m/y));
        ans+=(get(z)-get(i-1))%mod*x%mod*y%mod;
        ans%=mod;
        i=z;
    }
    return ans;
}


int main()
{
    RD(n,m);
    if(n>m) swap(n,m);
    i64 ans1=(n*n%mod-cal(n,n))%mod*(m*m%mod-cal(m,m))%mod;
    i64 ans2=n*n%mod*m%mod-n*cal(m,n)%mod-m*cal(n,n)%mod+cal(n,m,n)%mod;
    i64 ans=(ans1-ans2)%mod;
    if(ans<0) ans+=mod;
    PR(ans);
}





热门文章