BZOJ 1257 余数之和sum

时间:2021-07-09 11:13:36

题目链接:http://61.187.179.132/JudgeOnline/problem.php?id=1257

题意:计算sigama(m%i)(1<=i<=n)。

思路:

BZOJ 1257 余数之和sum

这样就简单了,若n*n<=m则可以直接暴力;否则,设t=sqrt(m),[1,t]之间暴力。在i大于t时我们发现,会出现成段的i使得m/i相同,那么我们直接枚举这个值i,那么L=m/(i+1)+1,R=m/i这个区间[L,R]的数字x均满足m/x=i,因此可以成段计算,复杂度也是O(sqrt(m))。

i64 n,m;

i64 cal()
{
    i64 ans=0,i;
    if(n<=100000)
    {
        FOR1(i,n) ans+=m/i*i;
        return ans;
    }
    i64 t=sqrt(1.0*m+0.5);
    FOR1(i,t) ans+=m/i*i;
    i64 L,R;
    FOR1(i,t)
    {
        L=m/(i+1)+1;
        R=m/i;
        if(L>n) continue;
        if(R>n) R=n;
        ans+=i*(L+R)*(R-L+1)/2;
    }
    return ans;
}

int main()
{
    while(scanf("%lld%lld",&n,&m)!=-1) PR(n*m-cal());
}