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;
}