题目描述:

给出正整数 nk,请计算
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 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注