luogu P2261 [CQOI2007]余数求和 |数论分块

题目描述

给出正整数 (n) 和 (k)，请计算

(G(n, k) = sum_{i = 1}^n k mod i)

其中 k mod ikmod ikmodi 表示 kkk 除以 iii 的余数。

输入格式

输入只有一行两个整数，分别表示 nnn 和 kkk。

输出格式

输出一行一个整数表示答案。

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
#define int long long
const int N=1e6+5;
signed main(){
	int n,k; cin>>n>>k;
	int ans=0;
	if(n>k)ans=(n-k)*k,n=k;
	ans+=n*k;

	for(int l=1,r=0;l<=n;l=r+1){
		r=min(k/(k/l),n);
		ans-=(k/r)*(r-l+1)*(l+r)/2;
	}
	cout<<ans<<endl;
}