【洛谷】P2261 [CQOI2007]余数求和

题面？？

点我获得题面QAQ

我这个咕儿终于在csp初赛前夕开始学习数论了！

我是绝对不会承认之前不学数学是因为去年刚开始学OI的时候就跟yyq他们学莫比乌斯反演然后自闭的

分析

对于k mod i，可以表示为$k-（k/i）*i$

所以答案就为

$$\sum_{i=1}^n k-(k/i)i$$

$$=nk-\sum_{i=1}^n (k/i)i$$

$\sum_{i=1}^n (k/i)i$这个东西可以用整除分块优化加上高斯求和搞（说得很高级似的

剩下的就很容易了

哇卡卡卡我总算学会用数学公式了

Code

#include<cstdio>

#include<algorithm>

using namespace std;

long long ans,n,k,l,r;

int main()

{

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

    while(r<=n)

    {

        l=r+;if(k/l==)break;r=k/(k/l);

        ans+=1ll*(l+min(n,r))*(min(r,n)-l+)*(k/l)/;

    }

    printf("%lld\n",n*k-ans);

}

巴特西

【洛谷】P2261 [CQOI2007]余数求和

题面？？

分析

最新文章

热门文章