中文题面
这道题就是 LightOJ 某题的升级版
前段时间我是直接用√k 前暴力后分块的处理方式，然后直接套个等差求和
这次看到了 dalao 的证明再次让我知道我好菜啊
在这里做下笔记，学习一下对于整除运算的分析方法
关于 \([\frac{k}{i}]×i,i∈[1,n]\) 的处理
令 \(x∈[1,k],g(x)=[k/[k/x]],f(x)=k/x\)
有 \(g(x) = [k/[f(x)]] ≥ [k/f(x)] = x\)
得到 \(g(x) ≥ x\)，换为底 \([k/g(x)]≤[k/x]\) ①
另一方面 \([k/g(x)] = [k/[k/[k/x]]] ≥ [k/k*[k/x]] = [k/x]\) ②
由①②可知 \(x∈[1,k]\)时，\([k/g(x)]=[k/x]\)
即对所有的 \(i∈[x,g(x)],[k/i]=[k/x]\)
即计算的规模取决于 \(i\)和\([k/i]\),
\(i≤\sqrt{k}\)时，计算规模为 \(\sqrt{k}\)（可认为 \(i\) 逐一计算）
\(i>\sqrt{k}\)时，计算规模为 \([k/i]\) 的不同的值，\(max{\ {[k/i]}\ }<\sqrt{k}\)，规模还是 \(\sqrt{k}\)（分段计算）
这也是之前可以暴力分块的依据，实际运算的时候要注意防止越界 (n)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int main(){
ll n,k,ans,gx,l,r,w,val;
while(cin>>n>>k){
ans=n*k;
for(int x=1; x<=n; x=gx+1){
val=k/x;
if(val==0) break;
gx=min(k/(k/x),n);
l=x,r=gx;
w=r-l+1;
ans -= val*(l+r)*w/2;
}
cout<<ans<<endl;
}
return 0;
}