UVA1363 约瑟夫的数论问题 题解

· · 题解

数论分块

常用于计算形如 \displaystyle \sum_{i=1}^{n}f(i)g(\lfloor\dfrac{n}{i}\rfloor) 的向下取整和式。大体思路是将 \lfloor\dfrac{n}{i}\rfloor 相同的值同时计算。时间复杂度为 O(\sqrt n)。

通过打表可以发现 \lfloor\dfrac{n}{i}\rfloor 的值呈块状分布，每个块内的值相等。每个块的左端点，就是上一个块的右端点 +1。对于右端点：

\because \lfloor\dfrac{n}{l}\rfloor=\lfloor\dfrac{n}{r}\rfloor \leq \dfrac{n}{r} \therefore r \le \dfrac{n}{\lfloor\dfrac{n}{l}\rfloor} \therefore r = \lfloor\dfrac{n}{\lfloor\dfrac{n}{l}\rfloor}\rfloor

至此，左端点和右端点全部求出，可以 O(1) 统计块内答案。

题解

显然 a \bmod b = a - b \lfloor\dfrac{a}{b}\rfloor。那么我们开始推式子：

\begin{aligned} & \sum_{i=1}^{n}k \bmod i \\ = & \sum_{i=1}^{n}(k-i\lfloor\frac{k}{i}\rfloor)\\ = & nk-\sum_{i=1}^{n}\lfloor\frac{k}{i}\rfloor\\ \end{aligned}

对于后面那坨，我们用数论分块求即可。注意多组数据和 long long。

代码

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;
ll n,k;
int main () {
    while(cin>>n>>k) {
    ll ans=n*k;
    for(int l=1,r;l<=n;l=r+1) {
        if(k/l) r=min(k/(k/l),n);
        else r=n;
        ans-=(k/l)*(r-l+1)*(l+r)>>1;
    }
    cout<<ans<<endl;
    }
    return 0;
}