BZOJ - 1257 分块 详解

中文题面
这道题就是LightOJ某题的升级版
前段时间我是直接用√k前暴力后分块的处理方式,然后直接套个等差求和
这次看到了dalao的证明再次让我知道我好菜啊
在这里做下笔记,学习一下对于整除运算的分析方法

关于[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≤√k时,计算规模为√k(可认为i逐一计算)
i>√k时,计算规模为[k/i]的不同的值,max{[k/i]}<√k,规模还是√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;
}