把横纵坐标按 n 分成完整块和残块，利用模 n 余数的一一配对，常数时间统计整块与右下角残块贡献。
OJ: luogu
题目 ID: P10090
难度:普及/提高-
标签:数学计数思维推导
日期: 2026-06-20 15:25
题意
给出 n,a,b，要求统计有多少对 (x,y) 满足：
0 <= x <= a0 <= y <= bx + y != 0x + y能被n整除
也可以把它理解成：
- 在一个
(a+1) * (b+1)的整数网格里； - 统计所有落在直线
x+y=kn上的整点； - 但要去掉原点
(0,0)。
思路
先看一个最直接的暴力程序：
cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int T;
int n, a, b;
i64 solve_one() {
i64 ans = 0;
for (int x = 0; x <= a; x++) {
for (int y = 0; y <= b; y++) {
if (x + y == 0) {
continue;
}
if ((x + y) % n == 0) {
ans++;
}
}
}
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--) {
cin >> n >> a >> b;
cout << solve_one() << '\n';
}
return 0;
}暴力版直接枚举所有点 (x,y)，检查：
x+y是否非零；(x+y) % n == 0是否成立。
它只能跑很小的数据，但特别适合验证公式。
把坐标按长度 n 分块
横坐标共有 a+1 个值，纵坐标共有 b+1 个值，所以先记：
cnt_x = a+1cnt_y = b+1
再分别除以 n：
cnt_x = block_x * n + rem_xcnt_y = block_y * n + rem_y
这就把整个大矩形分成了：
- 左上角很多个完整
n*n块 - 右侧残列
- 下方残行
- 右下角残块
为什么一个完整块恰好贡献 n
在一个完整 n*n 块中：
x mod n会把0..n-1各出现一次；y mod n也会把0..n-1各出现一次。
若要求：
x+y ≡ 0 (mod n)
那么对每个 x mod n = r，都恰好有唯一一个 y mod n = (-r mod n) 与之配对。
所以一个完整块里，合法点数正好是 n。
于是完整块总贡献是：
n * block_x * block_y
右侧残列和下方残行
先看右侧残列。
对于每一条完整横块：
x的每个余数都会完整出现一次；- 右边的每一列
y余数固定； - 所以每一列都恰好能找到一个合法的
x。
因此右侧残列总贡献是：
block_x * rem_y
同理，下方残行贡献是：
block_y * rem_x
右下角残块怎么数
这里只剩一个 rem_x * rem_y 的小矩形，需要单独处理。
在这里：
x的范围是[0, rem_x-1]y的范围是[0, rem_y-1]
因为 x,y < n，所以：
0 <= x+y <= 2n-2
若还要求 x+y ≡ 0 (mod n)，那么只可能出现两种情况：
x+y=0x+y=n
其中：
x+y=0只有(0,0)这一对；x+y=n的对数是max(0, rem_x + rem_y - n)。
所以右下角残块贡献是：
1 + max(0, rem_x + rem_y - n)
最后别忘了去掉 (0,0)
题目要求 x+y != 0，而整个矩形里只有 (0,0) 这一点会让 x+y=0。
所以我们可以：
- 先把
(0,0)也算进答案； - 最后统一减掉
1。
这样实现会更顺手。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
int T;
i64 n, a, b;
i64 solve_one() {
// 点的横坐标有 0..a，一共 a+1 个取值；
// 纵坐标有 0..b，一共 b+1 个取值。
i64 cnt_x = a + 1;
i64 cnt_y = b + 1;
i64 block_x = cnt_x / n;
i64 block_y = cnt_y / n;
i64 rem_x = cnt_x % n;
i64 rem_y = cnt_y % n;
// 一个 n * n 的完整块里：
// 每个 x mod n 都唯一对应一个合法的 y mod n，
// 所以恰好有 n 个点满足 x + y ≡ 0 (mod n)。
i64 ans = n * block_x * block_y;
// 完整横块 + 右侧残列。
// 对于每一行完整横块，x 的每个余数都会出现一次，
// 所以右侧 rem_y 列里，每列都能唯一配出一个合法 x。
ans += block_x * rem_y;
// 下方残行 + 完整竖块，同理。
ans += block_y * rem_x;
// 最右下角 rem_x * rem_y 的残块需要单独统计。
// 这里的余数范围分别是 [0, rem_x-1]、[0, rem_y-1]。
// 想要 x + y ≡ 0 (mod n)，由于 0 <= x+y <= 2n-2，
// 只可能是：
// 1. x + y = 0，对应点 (0,0)
// 2. x + y = n
//
// (0,0) 也先算进去，最后统一减掉即可。
i64 extra = 0;
if (rem_x > 0 && rem_y > 0) {
// 统计满足 x+y=n 的对数。
// x 的范围是 [0, rem_x-1]，y 的范围是 [0, rem_y-1]。
// 可行条件是：
// n-(rem_y-1) <= x <= rem_x-1
// 所以对数是 max(0, rem_x + rem_y - n - 1)。
extra = max(0LL, rem_x + rem_y - n - 1);
// 再加上 (0,0) 这一对。
extra += 1;
}
ans += extra;
// 题目要求 x+y 不为 0，所以删掉唯一的点 (0,0)。
ans -= 1;
return ans;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> T;
while (T--) {
cin >> n >> a >> b;
cout << solve_one() << '\n';
}
return 0;
}复杂度
- 时间复杂度：
- 空间复杂度：
总结
这题的关键，是把条件“x+y 是 n 的倍数”理解成余数配对问题。
一旦想到按 n 分块：
- 完整块的贡献会重复；
- 边缘长条也能直接算；
- 真正麻烦的只剩下右下角小残块。
最后就能把整题压成一个常数时间公式。