自动搬运

查看原文

来自洛谷，原作者为

	cff_0102 & aqua_qaq | 团子群 185800038 | 如果我死了说明我 AFO 了

搬运于2025-08-24 22:54:33，当前版本为作者最后更新于2024-01-22 18:49:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

把 $x$ 的范围拆成 $0\le x<\lfloor\dfrac{a}{n}\rfloor\times n$ 和 $\lfloor\dfrac{a}{n}\rfloor\times n\le x\le a$ 两个范围，把 $y$ 的范围拆成 $0\le y<\lfloor\dfrac{b}{n}\rfloor\times n$ 和 $\lfloor\dfrac{b}{n}\rfloor\times n\le y\le b$ 两个范围。那么 $x,y$ 的取值范围就有四种可能：设 $(p,q)$ 表示 $x$ 属于它的第 $p$ 个范围，$y$ 属于它的第 $q$ 个范围，则这四个可能分别是 $(1,1),(2,1),(1,2),(2,2)$。

然后分情况讨论。

• $(1,1)$：将 $x,y$ 的范围分别拆成 $\lfloor\dfrac{a}{n}\rfloor$ 和 $\lfloor\dfrac{b}{n}\rfloor$ 个大小为 $n$ 的小范围，那么只考虑 $x,y$ 分别在哪个范围的话，一共有 $\lfloor\dfrac{a}{n}\rfloor\times\lfloor\dfrac{b}{n}\rfloor$ 种可能。而在一个大小为 $n$ 的小范围中，$x$ 随便取其中一个，为了让加和结果是 $n$ 的倍数，$y$ 都有且只有一个数与其对应。因此，这样在每个小范围中，实际上有 $n$ 种 $x,y$ 的取值可能。乘上前面范围的可能，此时的可能数为 $\lfloor\dfrac{a}{n}\rfloor\times\lfloor\dfrac{b}{n}\rfloor\times n$ 种。
• $(2,1)$：将 $y$ 的范围拆成 $\lfloor\dfrac{b}{n}\rfloor$ 个大小为 $n$ 的小范围，那么只考虑 $y$ 在哪个范围的话，一共有 $\lfloor\dfrac{b}{n}\rfloor$ 种可能。而在一个大小为 $a\bmod n$ 的小范围中，$x$ 随便取其中一个，为了让加和结果是 $n$ 的倍数，$y$ 都有且只有一个数与其对应。因此，这样在每个小范围中，实际上有 $a\bmod n$ 种 $x,y$ 的取值可能。乘上前面范围的可能，此时的可能数为 $\lfloor\dfrac{b}{n}\rfloor\times(a\bmod n)$ 种。
• $(1,2)$：将 $x$ 的范围拆成 $\lfloor\dfrac{a}{n}\rfloor$ 个大小为 $n$ 的小范围，那么只考虑 $x$ 在哪个范围的话，一共有 $\lfloor\dfrac{a}{n}\rfloor$ 种可能。而在一个大小为 $b\bmod n$ 的小范围中，$y$ 随便取其中一个，为了让加和结果是 $n$ 的倍数，$x$ 都有且只有一个数与其对应。因此，这样在每个小范围中，实际上有 $b\bmod n$ 种 $x,y$ 的取值可能。乘上前面范围的可能，此时的可能数为 $\lfloor\dfrac{a}{n}\rfloor\times(b\bmod n)$ 种。
• $(2,2)$：在一个大小为 $a\bmod n$ 的小范围中，$x$ 随便取一个数，为了让加和结果是 $n$ 的倍数，$y$ 必须为 $n-x$。此时必须要求 $n-x$ 在 $y$ 的范围内，即 $0\le n-x\le b\bmod n$。那么，答案应该是满足 $0\le n-x\le b\bmod n$ 且 $0\le x\le a\bmod n$ 的 $(x,y)$ 个数。化简一下前者，得到 $n-b\bmod n\le x\le n$。因为 $a\bmod n<n,n-b\bmod n>0$，所以两式合并得到 $n-b\bmod n\le x\le a\bmod n$。此时答案就是满足这个条件的 $x$ 的数量。因此，有 $\max(0,a\bmod n-(n-b\bmod n)+1)=\max(0,a\bmod n+b\bmod n-n+1)$ 种 $x,y$ 的取值可能。

所以答案就是上面四种情况的答案之和，即 $\lfloor\dfrac{a}{n}\rfloor\times\lfloor\dfrac{b}{n}\rfloor\times n+\lfloor\dfrac{b}{n}\rfloor\times(a\bmod n)+\lfloor\dfrac{a}{n}\rfloor\times(b\bmod n)+\max(0,a\bmod n+b\bmod n-n+1)$ 种可能的情况。

t=int(input())
for _ in range(t) :
    n,a,b=map(int,input().split())
    print((a//n)*(b//n)*n + (a%n+1)*(b//n) + (b%n+1)*(a//n) + max(0,a%n+b%n-n+1))