题目描述:
给出正整数 n 和 k,请计算
G(n, k) = \sum_{i = 1}^n k \bmod i
其中 k\bmod i 表示 k 除以 i的余数。
n,k\leq10^9
Solution:
有
k \bmod i= k-\lfloor \frac{k}{i} \rfloor*i
利用整除分块将 \lfloor \frac{k}{i} \rfloor 分为一块,利用等差数列即可在 O(\sqrt{n}) 的复杂度求出答案
#include<bits/stdc++.h>
#define ll long long
ll n,k;
ll t;
int main(){
scanf("%lld%lld",&n,&k);
ll ans=0;
if(n>k) ans+=1ll*k*(n-k);
n=std::min(n,k);
for(ll l=1,r;l<=n;l=r+1){
r=k/(k/l);
r=std::min(n,r);
ans+=k*(r-l+1)-(r-l+1)*(r+l)/2*(k/l);
t++;
}
printf("%lld",ans);
return 0;
}
0 条评论