一道数论分块
首先这类的求和写一下公式
∑n%i=∑n-i*(n/i)=
∑n-∑i*(n/i)
前面的好求所以
ans=nk+∑k*(k/i);
于是进行分块
这里总结一下
只要出现除法∑就进行分块
由阿尔贝和推论
加号后面的也等于
(∑i)(∑(k/【i】-k+1/【i】))(阿尔贝恒等式)
这样是不是更显然了
∑i等差数列求和
后面的参见我的数论分块另一个博客#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
#define ll long long
int main() {
ll n,k;
cin>>n>>k;
ll ans=n*k;
for(ll l=,r;l<=n;l=r+) {
if(k/l!=) r=min(k/(k/l),n);
else r=n;
ans-=(k/l)*(r-l+)*(l+r)/;
}
cout<<ans;
return ;
}