【CQOI 2009】余数之和

【题目链接】

https://www.lydsy.com/JudgeOnline/problem.php?id=1257

【算法】

k mod i = k - [k / i] * i

所以 (k mod 1) + (k mod 2) + ... + (k mod n) = nk - sigma([k/i] * i) (1 <= i <= n)

[k/i] 至多有sqrt(k)个不同的值，利用这个性质，用等差数列进行计算即可

【代码】

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

ll n,k,x,gx,ans;

int main() {

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

        ans = n * k;

        for (x = ; x <= n; x = gx + )

        {

                gx = k / x ? min(k/(k/x),n) : n;

                ans -= (k / x) * (x + gx) * (gx - x + ) / ;

        }

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

        return ;

}

巴特西

【CQOI 2009】余数之和

最新文章

热门文章

巴特西

【CQOI 2009】 余数之和

最新文章

热门文章

【CQOI 2009】余数之和