P10090 [ROIR 2022 Day 2] 幼儿园的新年 题解

· · 题解

把 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)。

然后分情况讨论。

所以答案就是上面四种情况的答案之和，即 \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))