中文题面

这道题就是 LightOJ 某题的升级版

前段时间我是直接用√k 前暴力后分块的处理方式，然后直接套个等差求和

这次看到了 dalao 的证明再次让我知道我好菜啊

在这里做下笔记，学习一下对于整除运算的分析方法

关于 $[\frac{k}{i}]\times i,i\in [1,n]$ 的处理

令 $x\in [1,k],g(x)=[k/[k/x]],f(x)=k/x$

有 $g(x)=[k/[f(x)]]\ge [k/f(x)]=x$

得到 $g(x)\ge x$，换为底 $[k/g(x)]\le [k/x]$ ①

另一方面 $[k/g(x)]=[k/[k/[k/x]]]\ge [k/k\ast [k/x]]=[k/x]$ ②

由①②可知 $x\in [1,k]$时，$[k/g(x)]=[k/x]$

即对所有的 $i\in [x,g(x)],[k/i]=[k/x]$

即计算的规模取决于 $i$和$[k/i]$,

$i\le \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;
}