【[ABC414E] Count A%B=C】题解

· · 题解

思路

先分析条件。

  1. a\bmod b=c

    一个 a 和一个 b 对应一个 c。

  2. 1\le a,b,c\le N

    限定了 a,b,c 的范围，以及 b\nmid a。

  3. 限定了 $a>b$。

考虑一个 b 对答案的贡献，即 \lparen b,N\rbrack 范围内不是 b 的倍数的整数个数，即 N-(b-1)-\left\lfloor\frac{N}{b}\right\rfloor。

则答案为：

\begin{align*} &\sum_{i=1}^N\left[N-(i-1)-\left\lfloor\frac{N}{b}\right\rfloor\right] \\ =&N^2-\sum_{i=1}^N(i-1)-\sum_{i=1}^N\left\lfloor\frac{N}{b}\right\rfloor \\ =&N^2-\frac{N(N-1)}{2}-\sum_{i=1}^N\left\lfloor\frac{N}{b}\right\rfloor \\ =&\frac{N^2+N}{2}-\sum_{i=1}^n\left\lfloor\frac{N}{b}\right\rfloor \end{align*}

前一项可以 \Omicron\left(1\right) 计算，后一项可以使用数论分块（\text{aka} 根号分治，不知道怎么用的参见 UVA11526）在 \Omicron\left(\sqrt{N}\right) 时间复杂度内计算，总时间复杂度 \Omicron\left(\sqrt{N}\right)。

注意事项

  1. 十年 OI 一场空，不开 __ 见祖宗；
  2. 模意义下的除法用逆元。

AC Code

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MOD = 998244353, I = 499122177;
// I 为 2 模 998244353 意义下的逆元。
ll n, ans;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    ll l = 1, r = 0;
    for(; l <= n; l = r + 1){
        r = n / (n / l);
        ans -= ((r - l + 1) % MOD) * ((n / l) % MOD) % MOD;
        ans = (ans % MOD + MOD) % MOD;
    } // 数论分块
    n %= MOD;
    ans += (((n * n % MOD) + n) % MOD) * I % MOD;
    ans %= MOD;
    cout << ans;
}