参考：题解

令f(i)=k%i,[p]表示不大于p的最大整数
f(i)=k%i=k-[k/i]*i
令q=[k/i]
f(i)=k-qi
如果k/(i+1)=k/i=q
f(i+1)=k-q(i+1)=k-qi-q=f(i)-q
于是，对于区间[l,r]，使其之内任意两个整数i,j，都满足k/i=k/j，
则f(l)到f(r)是一个递减的等差数列，公差为[k/i]。
现在就是要把1到n分成这样的一些区间，设某个区间的商（公差）为p
设区间内某数为x，则现在要做的是解方程[k/x]=p
显然px<=k，因此x<=k/p，得出这个区间的最大的x也就是r=[k/p]，
显然，l=[k/(p+1)]+1
数的个数为r-l+1

 #include<cstdio>

 typedef long long LL;

 LL ans,n,k;

 LL min(LL a,LL b)

 {

     return a>b?b:a;

 }

 int main()

 {

     LL r;

     scanf("%lld%lld",&n,&k);

 //    LL minp=k/n,p;

 //    LL maxp=min(n,k);

 //    for(p=minp;p<=maxp;p++)

 //    {

 //        l=k/(p+1)+1;

 //        if(p==0)

 //            r=n;

 //        else

 //            r=min(n,k/p);

 //        if(l<=r)

 //        {

 //            ans+=(r-l+1)*(k%l+k%r)/2;

 //        }

 //    }//太慢了，时间复杂度还是接近O(n)，有大量多余循环

     LL p,q;

     for(int i=;i<=n;i++)

     {

         //此处能循环到的i就是上面方法的l

         p=k/i;

         q=k%i;

         //从i开始的区间，r就是min(n,[k/(k/i)])

         if(p==)

             r=n;

         else

             r=min(n,k/p);

         ans+=(r-i+)*(q+k%r)/;

         i=r;

     }

     printf("%lld",ans);

     return ;

 }

这可以称为整除分块例题了。。。

$$\sum_{i=1}^nk\%i=\sum_{i=1}^n(k-i*{\lfloor}{\frac{k}{i}}{\rfloor})=n*k-\sum_{i=1}^n(i*{\lfloor}{\frac{k}{i}}{\rfloor})$$

最后的那个直接整除分块即可。。。

整除分块的话，就是因为${\lfloor}{\frac{k}{i}}{\rfloor}(i为整数且1<=i<=k)$的值只有$\sqrt{k}$级别个

原因：对于小于等于$\sqrt{k}$的i，每一个产生一个${\lfloor}{\frac{k}{i}}{\rfloor}$，最多产生$\sqrt{k}$个；对于大于$\sqrt{k}$的i，产生的${\lfloor}{\frac{k}{i}}{\rfloor}$都小于$\sqrt{k}$，最多有$\sqrt{k}$个。合起来也是$\sqrt{k}$级别个

那么只要枚举每一种${\lfloor}{\frac{k}{i}}{\rfloor}$，根据要求的式子的一些性质计算即可

（比如此题就是在${\lfloor}{\frac{k}{i}}{\rfloor}$相等时就相当于$p*\sum_{i=l}^ri$，$p$为那个${\lfloor}{\frac{k}{i}}{\rfloor}$）

当然不太可能直接枚举每一种${\lfloor}{\frac{k}{i}}{\rfloor}$，事实上还是枚举i，然后直接从i"跳"到j，使得j是满足${\lfloor}{\frac{k}{j}}{\rfloor}$与${\lfloor}{\frac{k}{i}}{\rfloor}$相等的最大数

如何跳？设${\lfloor}{\frac{k}{j}}{\rfloor}=p$，则$p+1>{\frac{k}{j}}>=p$，则$j*(p+1)>k>=p*j$，则${\frac{k}{p+1}}<j<={\frac{k}{p}}$

因此枚举出一个i后，$p={\lfloor}{\frac{k}{i}}{\rfloor}$，那么要跳到的j就是${\lfloor}{\frac{k}{{\lfloor}{\frac{k}{i}}{\rfloor}}}{\rfloor}$

好吧，对于此题要加一个特判，因为n可能大于k，此时不能直接用原来代码，而i为整数且k<i<=n时${\lfloor}{\frac{k}{i}}{\rfloor}$的值为0，因此跳过即可；还有要"跳"到的j要和n取min

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 ll n,k,ans;

 int main()

 {

     ll i,j;

     scanf("%lld%lld",&n,&k);ans=n*k;

     for(i=;i<=min(n,k);i=j+)

     {

         j=min(n,k/(k/i));//注意对n取min

         ans-=(k/i)*(i+j)*(j-i+)/;

     }

     printf("%lld",ans);

     return ;

 }