问题描述:

给出正整数$n$和$k$,计算$G(n, k) =k  \% 1 + k \% 2 + … + k \% n$的值。

输入:

输入仅一行,包含两个整数$n$, $k$ ($1<=n, k<=10^9$)

输出:

输出仅一行,即$j(n, k)$。

思路:

直接计算原式肯定是会T的。。。我们可以根据 $a  \%  b=a-\lfloor a/b \rfloor *b$ 将原式变形。所以答案可以在$n*k$的基础上减去上式的后一部分得到。然后我们可以发现 $\lfloor a/b \rfloor$ 的取值是一段一段的,所以可以对于每一段用等差数列求和的公式得出答案。

复杂度似乎是$O( \sqrt{n} )$的

代码:

#include 
#define LL long long
using namespace std;

LL n, k, ans;

int main()
{
    scanf("%lld%lld", &n, &k);
    ans=n*k;
    if(n>k) n=k;
    for(LL l=1, r; l<=n; l=r+1)
    {
        LL temp=k/l; r=min(k/temp, n);
        ans-=temp*(l+r)*(r-l+1)/2;
    }
    printf("%lld\n", ans);
}

发表评论

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