前几天在qbxt的时候,好像做到了一道数论分块的题目
那时候只知道有些区间内的的结果是一样的。
然后今天闲来无聊,翻到了这道题。发现是数论分块。就尝试学习了一下
(都快noip了你学这个没有的玩意干什么?)
感觉差不多遇到取模的题(在我这个等级qwq),最难也就是个数论分块的板子
学学吧
记得在学(exgcd)的时候,曾将(a%b)转化为$a-bcdot lfloor frac{a}{b} floor $的形式
这个题一样可以(large{sum_{i=1}^n} k-lfloor frac{k}{i} floor cdot i)
然后这个$lfloor frac{k}{i} floor $可以分块处理的,就是可能在一段区间内,这个玩意都是不变的。
然后如何快速算出这个区间的和呢?使用平均数。
于是就有了下面的代码
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
using std::min;
int main()
{
long long n,k,ans=0;
scanf("%lld%lld",&n,&k);
ans=n*k;
for(long long l=1,r;l<=n;l=r+1)//l/r 当前处理的区间
{
if(k/l!=0)
r=min(n,k/(k/l));//根据积算出右端点
else
r=n;//终止
ans=ans-(k/l)*(r-l+1)*(l+r)/2LL;//平均数一稿
}
printf("%lld",ans);//输出
}