Acwing199.余数之和（数学+思维）xiaodangao

给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值。

例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7。

输入格式

输入仅一行，包含两个整数n, k。

输出格式

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

数据范围

$1 \le n,k \le 10^9$

输入样例：

5 3

输出样例：

思路：看了大神的代码才学会的，方法是分块:
$j(n,k) = \displaystyle\sum_{i=1}^n(k- \lfloor \frac{k}{i} \rfloor * i) = n*k - \sum_{i=1}^n(\lfloor \frac{k}{i} \rfloor * i)$
然后我们根据式子可以发现，难点在于 $\lfloor \frac{k}{i} \rfloor$ 的求法，可以看出来 $\lfloor \frac{k}{i} \rfloor$ 的值在i变化时可能不会发生改变，所以我们思考是否能够通过求 $\lfloor \frac{k}{i} \rfloor$ 的变化范围进而求值。想到这一步必须先证明 $\lfloor \frac{k}{i} \rfloor$ 中的值的确是很有限的，与 $n$ 不在一个量级上，事实证明确实是这样的，考虑 $i$ 的取值从 $1-\sqrt k$ 的情况，因为该段有 $\sqrt k$ 个取值，所以在该段的 $\lfloor \frac{k}{i} \rfloor$ 最多有 $\sqrt k$ 个取值，然后考虑 $\sqrt k-k$ 的情况，观察 $\lfloor \frac{k}{i} \rfloor$ 发现当 $i$ 取 $\sqrt k->k$ 时 $\lfloor \frac{k}{i} \rfloor \leq \sqrt k$ 那就证明了在 $\sqrt k->k$ 段上，也最多仅有 $\sqrt k$ 个取值；
然后我们现在就是求对于 $\lfloor \frac{k}{i} \rfloor$ 的每一个取值的上下界，设一个取值的下界是 $x$ 那么上界会是什么呢？
设 $a*b = k$ （左边不一定是整数）观察到我们如果想让 $b$ 的取值不发生变化，那么我们取 $\lfloor b \rfloor$ 能得到最大的 $a$ ，这里的思路也是这样，上界取 $\lfloor k/\lfloor k/x \rfloor \rfloor$ 这里 $\lfloor k/b \rfloor$ 就代表这个 $\lfloor b \rfloor$ 的取值；
随后再加一个等差数列求和公式；
$Code:$


/*************************************************************************
    > File Name: Acwing.cpp
# Author: Badwoman
# mail: 1194446133@qq.com
    > Created Time: 2020年12月21日 星期一 10时41分06秒
 ************************************************************************/

#include<set>
#include<iostream>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<map>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define bep(i,a,b) for(int i=a;i>=b;--i)
#define lowbit(x) (x&(-x))
using namespace std;
ll n,k;
void solve(){
    scanf("%lld%lld",&n,&k);
    ll ans = n*k,r;
    for(ll l=1;l<=n;l = r+1){
        if(k/l == 0)break;
        r = min(n,k/(k/l));
        ll p = k/l;
        ans -= p*(r-l+1)*(l+r)/2;
    }
    printf("%lld\n",ans);
}
int main(){
    solve();
    return 0;
}

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。