余数之和 解题报告

解题报告

算法进阶指南 余数之和

题意

给定正整数 $n,k$ $(1 \le n,k \le 10^9)$,
求 $\sum_{i=1}^{n} k \bmod i$.

思路

$k \bmod i$ 可以变为 $k - \lfloor \frac{k}{i} \rfloor * i$,
$\lfloor \frac{k}{i} \rfloor$ 这一坨可以数论分块, 每次再求个等差序列和就好了.

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,x;
ll ans;
ll sum(ll a,ll b){ return (a+b)*(b-a+1)/2; }
int main(){
//  freopen("som.in","r",stdin);
    cin>>n>>x;
    for(int i=1;i*i<=x;i++){
        if(i<=n&&x/i!=i){ ans+=x%i; }
        if(x/(i+1)>=n) continue;
        int a=min(x/i,n),b=x/(i+1)+1;
        ans+=(ll)(a-b+1)*x-sum((ll)b,(ll)a)*i;
    }
    if(n>x) ans+=(ll)(n-x)*x;
    printf("%lld\n",ans);
    return 0;
}