专栏文章

CF1485C Floor and Mod

AAutream
CF1485C题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miovuc1t
此快照首次捕获于
2025/12/03 01:59
3 个月前
此快照最后确认于
2025/12/03 01:59
3 个月前
查看原文

题意简述

对于所有 a∈[1,x],b∈[1,y]a \in [1, x], b\in[1, y] 求 ⌊ab⌋=amod⁡b\lfloor \frac{a}{b} \rfloor = a \operatorname{mod} b 的数对 (a,b)(a, b) 的个数。

题目分析

评蓝高了，CF 上都只有 1700。
使用瞪眼法容易发现以下几个性质：
  1. a>ba > b；
  2. y=min⁡{x,y}y = \min\{x,y\}；
  3. 对于任意合法的 bb 取值，满足条件的 (a,b)(a, b) 最多只有 b−1b - 1 个（除 00 以外，bb 的余数只有 b−1b - 1 个）。
根据以上性质容易发现，能把一个 bb 的所有数对都取完的条件是 xb≥b\frac{x}{b} \ge b，即 b≤xb \le \sqrt x。
对于剩下的 b∈(x,y]b \in (\sqrt x, y]，此时 xb<b\frac{x}{b} < b，它们对答案的贡献即为 xx 整除它们的商。
考虑枚举这个商。由于是整除，所以自然想到整除分块。
具体地，对于枚举的 i∈[1,⌊xx⌋)i \in [1, \lfloor \frac{x}{\sqrt x} \rfloor)，商均为 ii 的数即为 (⌊xi+1⌋,⌊xi⌋](\lfloor \frac{x}{i + 1} \rfloor, \lfloor \frac{x}{i} \rfloor] 中的数（根据 yy 调整上界），贡献显然。
时间复杂度 O(V)O(\sqrt V)。

代码

CPP
CI N = 2e5 + 5;
int T, x, y, ans;
signed main() {
	T =  read();
	while(T --) {
		x = read(), y = std::min(x, read()), ans = 0;
		rep(i, 2, std::min(y, (int)std::sqrt(x))) ans += i - 1;
		dep(i, x / (int)std::sqrt(x) - 1, 1) if(x / i ^ x / (i + 1)) {
			if(x / (i + 1) >= y) break;
			ans += i * (std::min(y, x / i) - x / (i + 1)) - (y >= x / i);
		}
		printl(ans);
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...