bzoj 1257 [CQOI2007]余数之和——数论分块

时间:2023-03-08 23:38:53
bzoj 1257 [CQOI2007]余数之和——数论分块

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

\( n\%i = n - \left \lfloor n/i \right \rfloor * i \)

注意 n<k 时当前块的右端点可能超过 n !

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int n,k;ll ans;
int main()
{
scanf("%d%d",&n,&k);
int lm=min(n,k);
for(int i=,j,d;i<=lm;i=j+)
{
d=k/i; j=min(k/d,n);//min!!!
ans+=(ll)d*(i+j)*(j-i+)>>1ll;
}
printf("%lld\n",(ll)n*k-ans);
return ;
}