前几天在qbxt的时候，好像做到了一道数论分块的题目

那时候只知道有些区间内的的结果是一样的。

然后今天闲来无聊，翻到了这道题。发现是数论分块。就尝试学习了一下

（都快noip了你学这个没有的玩意干什么？）

感觉差不多遇到取模的题（在我这个等级qwq），最难也就是个数论分块的板子

学学吧

---

记得在学\(exgcd\)的时候，曾将\(a%b\)转化为$a-b\cdot \lfloor \frac{a}{b} \rfloor $的形式

这个题一样可以\(\large{\sum_{i=1}^n} k-\lfloor \frac{k}{i} \rfloor \cdot i\)

然后这个$\lfloor \frac{k}{i}\rfloor $可以分块处理的，就是可能在一段区间内，这个玩意都是不变的。

然后如何快速算出这个区间的和呢？使用平均数。

于是就有了下面的代码

#include
    
     #include
     
      #include
      
       #include
       
        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);//输出}