参考：题解
令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
1 #include<cstdio> 2 typedef long long LL; 3 LL ans,n,k; 4 LL min(LL a,LL b) 5 { 6 return a>b?b:a; 7 } 8 int main() 9 { 10 LL r; 11 scanf("%lld%lld",&n,&k); 12 // LL minp=k/n,p; 13 // LL maxp=min(n,k); 14 // for(p=minp;p<=maxp;p++) 15 // { 16 // l=k/(p+1)+1; 17 // if(p==0) 18 // r=n; 19 // else 20 // r=min(n,k/p); 21 // if(l<=r) 22 // { 23 // ans+=(r-l+1)*(k%l+k%r)/2; 24 // } 25 // }//太慢了，时间复杂度还是接近O(n)，有大量多余循环 26 LL p,q; 27 for(int i=1;i<=n;i++) 28 { 29 //此处能循环到的i就是上面方法的l 30 p=k/i; 31 q=k%i; 32 //从i开始的区间，r就是min(n,[k/(k/i)]) 33 if(p==0) 34 r=n; 35 else 36 r=min(n,k/p); 37 ans+=(r-i+1)*(q+k%r)/2; 38 i=r; 39 } 40 printf("%lld",ans); 41 return 0; 42 }
这可以称为整除分块例题了。。。
$$sum_{i=1}^nk\%i=sum_{i=1}^n(k-i*{lfloor}{frac{k}{i}}{ floor})=n*k-sum_{i=1}^n(i*{lfloor}{frac{k}{i}}{ floor})$$
最后的那个直接整除分块即可。。。
整除分块的话，就是因为${lfloor}{frac{k}{i}}{ floor}(i为整数且1<=i<=k)$的值只有$sqrt{k}$级别个
原因：对于小于等于$sqrt{k}$的i，每一个产生一个${lfloor}{frac{k}{i}}{ floor}$，最多产生$sqrt{k}$个；对于大于$sqrt{k}$的i，产生的${lfloor}{frac{k}{i}}{ floor}$都小于$sqrt{k}$，最多有$sqrt{k}$个。合起来也是$sqrt{k}$级别个
那么只要枚举每一种${lfloor}{frac{k}{i}}{ floor}$，根据要求的式子的一些性质计算即可
（比如此题就是在${lfloor}{frac{k}{i}}{ floor}$相等时就相当于$p*sum_{i=l}^ri$，$p$为那个${lfloor}{frac{k}{i}}{ floor}$）
当然不太可能直接枚举每一种${lfloor}{frac{k}{i}}{ floor}$，事实上还是枚举i，然后直接从i"跳"到j，使得j是满足${lfloor}{frac{k}{j}}{ floor}$与${lfloor}{frac{k}{i}}{ floor}$相等的最大数
如何跳？设${lfloor}{frac{k}{j}}{ floor}=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}}{ floor}$，那么要跳到的j就是${lfloor}{frac{k}{{lfloor}{frac{k}{i}}{ floor}}}{ floor}$
好吧，对于此题要加一个特判，因为n可能大于k，此时不能直接用原来代码，而i为整数且k<i<=n时${lfloor}{frac{k}{i}}{ floor}$的值为0，因此跳过即可；还有要"跳"到的j要和n取min
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #include<vector> 5 using namespace std; 6 #define fi first 7 #define se second 8 #define mp make_pair 9 #define pb push_back 10 typedef long long ll; 11 typedef unsigned long long ull; 12 typedef pair<int,int> pii; 13 ll n,k,ans; 14 int main() 15 { 16 ll i,j; 17 scanf("%lld%lld",&n,&k);ans=n*k; 18 for(i=1;i<=min(n,k);i=j+1) 19 { 20 j=min(n,k/(k/i));//注意对n取min 21 ans-=(k/i)*(i+j)*(j-i+1)/2; 22 } 23 printf("%lld",ans); 24 return 0; 25 }