BZOJ-2956: 模积和

Description

求n,m<=10^9。

mod 转化为然后分块求解，最后减去i,j相同的值，需要计算平方和（小trick：÷6直接取模6*mod）。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll mod=19940417;
ll n,m;
ll solve(int x)
{
    ll b=1,e,re=0;
    while(b<=x)
    {
        e=x/(x/b);
        re=(re+x*(e-b+1)%mod)%mod;
        re=(re-(e+b)*(e-b+1)/2%mod*(x/b)%mod+mod)%mod;
        b=e+1;
    }
    return re;
}
inline ll getsum(ll x){return x*(x+1)%(6*mod)*(2*x+1)/6%mod;}
int main()
{
    scanf("%lld%lld",&n,&m); if(n>m) swap(n,m);
    ll ans=solve(n)*solve(m)%mod;
    ans=(ans-n*m%mod*n%mod+mod)%mod;
    ll b=1,e;
    while(b<=n)
    {
        e=min(n/(n/b),m/(m/b));
        ans=(ans+(n*(m/b)+m*(n/b))%mod*((e+b)*(e-b+1)/2%mod)%mod)%mod;
        ans=(ans-(n/b)*(m/b)%mod*( ( getsum(e)-getsum(b-1)+mod )%mod )%mod+mod)%mod;
        b=e+1;
    }
    printf("%lld",ans);
    return 0;
}