BZOJ1257: [CQOI2007]余数之和—

题意

求 $\sum _{i=1}^n k \ mod \ i$（$1\leq n,k\leq 10^9$）.

分析

数据范围这么大 $O(n)$ 的复杂度也挺不住啊

根据取模的意义，$k \ mod \ i = k - \left \lfloor \frac{k}{i} \right \rfloor * i$，

因此可以用整除分块，注意分类讨论 $k$ 与 $n$ 的关系。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

int n, k;

ll solve()

{

    ll ret = 1LL * n * k;

    if(k <= n)   //需要分类讨论

    {

        for(int i = ,j;i <= k;i = j+)

        {

            j = k / (k / i);

            ret -= 1LL * (i+j) * (j-i+) /  * (k / i);

        }

    }

    else

    {

        for(int i = ,j;i <= n;i = j+)

        {

            j = min(k / (k / i), n);

            ret -= 1LL * (i+j) * (j-i+) /  * (k / i);

        }

    }

    return ret;

}

int main()

{

    scanf("%d%d", &n, &k);

    printf("%lld\n", solve());

    return ;

}

参考链接：https://zhuanlan.zhihu.com/p/77687419

巴特西

BZOJ1257: [CQOI2007]余数之和——整除分块

题意

分析

最新文章

热门文章