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

思路

先分析条件。

$a\bmod b=c$
一个 $a$ 和一个 $b$ 对应一个 $c$ 。
$1\le a,b,c\le N$
限定了 $a,b,c$ 的范围，以及 $b\nmid a$ 。
$a,b,c$ 各不相同
限定了 $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)

。

注意事项

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

AC Code

CPP

#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;
}

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

文章操作

思路

注意事项

AC Code

相关推荐

评论

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