ACM/ICPC 2009 合肥现场赛 Laser in Cuboids 题解
这道题的题意是，问一个由单位正方体垒成的 A × B × C 的长方体的体对角线穿过了这个长方体中的几个单位正方体。如果对角线与正方体擦肩而过的话不算穿过。
怎么说呢，这道题纠结了几天，网上没有题解，只有模糊地提到容斥原理。在昨晚出去逛街的时候想到了二维的情况，如果长方形的大小是 A × B 的话，如果 A 和 B 互质，那么可以看出来，对角线穿过了 A + B – 1 个小正方形。如果 A 和 B 不互质，就求最大公约数 G, 令 A’ = A / G, B’ = B / G, 这么说在对角线上有 G 个 A’ × B’ 的长方形，对角线穿过了 (A’ + B’ – 1) × G 个小正方形。
推广到三维的时候就搞错了，当时想到的是，把能够从面 A 看到的小正方形的集合记为 A, 从面 B 和面 C 看到的也记为相应字母，然后能够同时从面 A 和面 B 看到的小正方形集合记为 A∩B, 类似。这样就有容斥原理了：
card(A∪B∪C) = card(A) + card(B) + card(C) – card(A∩B) – card(B∩C) – card(C∩A) + card(A∩B∩C).
在计算 card(A) 之类的东西的时候，可以用二维的方法。但是在计算 card(A∩B) 之类的时候，我一开始用的是 min(card(A), card(B)), 但是后来举出了反例，所以这种方法最后还是错了。
最后实在忍不住了，我就想应该问问当年区域赛 AC 过这题的前辈们。在看到的几份 Regional 总结中，我发现大家都说这题和当年该赛区热身赛里的一题非常像，当时的情景是几乎所有队都是齐刷刷地 AC 了这题。所以我想这也可能是这题题解较少的原因，因为当年可能大家都把它当成水题看待了……
凌晨一点多的时候在 watashi 大牛的博客留言请教，没想到十多分钟就有了解答，感激涕零……
这种思路还是需要一定的空间想象力，方法其实就是之前二维做法的推广，证明起来有点难，不过反正我是信了……
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 | #include <cstdio> #include <algorithm> using namespace std; template <typename T> T gcd(T a, T b) { T r; while (b > 0) { r = a % b; a = b; b = r; } return a; } template <typename T> T gcd(T a, T b, T c) { return gcd(a, gcd(b, c)); } int main() { int a, b, c, r; while (scanf("%d %d %d", &a, &b, &c)) { if (a == 0 && b == 0 && c == 0) break; r = a + b + c - gcd(a, b) - gcd(b, c) - gcd(c, a) + gcd(a, b, c); printf("%d\n", r); } return 0; } |
