C/C++教程

luogu P2261 [CQOI2007]余数求和 (数论分块)

本文主要是介绍luogu P2261 [CQOI2007]余数求和 (数论分块)，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

这题要推一下式子，注意涉及到取模的式子都要尽量展成减去下取整的形式。

 

 

注意，这里求和符号是求到n，因此分块里面 l 的范围就是l<=n，然后对于n大于k的情况需要特判一下。

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 LL n,k;
 5 int main(){
 6     LL i,j;
 7     LL l,r,ans=0ll;
 8     scanf("%lld%lld",&n,&k);
 9     ans=n*k;
10     for (l=1;l<=n;l=r+1){
11         if (k/l!=0) r=min(n,(k/(k/l)));
12         else r=n;
13         ans-=(k/l)*(r-l+1)*(r+l)/2;
14     }
15     printf("%lld",ans);
16     return 0;
17 }

 

这篇关于luogu P2261 [CQOI2007]余数求和 (数论分块)的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航