luogu P2261 [CQOI2007]餘數求和 (數論分塊)

這題要推一下式子，注意涉及到取模的式子都要盡量展成減去下取整的形式。

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