alan23273850 的刷題筆記
a810: 1. 倍數關係
Tags: math
出處：https://zerojudge.tw/ShowProblem?problemid=a810
提交：https://zerojudge.tw/Submissions?problemid=a810&account=allllllan123456
問題：輸入四個整數 $a, b, x, y\in[-10^{18}, 10^{18}]$ 其中 $a < b$，問你在數線上的區間 $[a,b]$ 內包含了幾個 $x$ 或 $y$ 的倍數？
解法：一個標準作法是先讓 $x$ 和 $y$ 都取絕對值變成正的。要計算一個區間 $[a,b]$ 包含幾個 $n$ 的倍數，可以先試著找到最小但不 $\lt a$ 的倍數點 $a'=n\cdot q_a$ 以及最大但不 $\gt b$ 的倍數點 $b'=n\cdot q_b$，那麼當 $a'\le b'$ 的時候，個數即為 $q_b - q_a + 1$，否則個數是 0，下方程式碼的 rightEP(b,n) 就是在算 $q_b$，而 leftEP(a,n) 就是在算 $q_a$，EP 是 endpoint 的意思。那只要統計 $x$ 的倍數的個數加上 $y$ 的倍數的個數，再扣掉 $x$ 和 $y$ 的最小公倍數的個數就是答案囉。這題的難點有三個，一個是 EP 的推導，負數的 floor 轉成正數的 ceil 再掛負號會比較好算，同理負數的 ceil 轉成正數的 floor 再掛負號也會比較好算。第二個是最小公倍數 overflow 的處理，因為這題給的數據逼近有效上界，要算最小公倍數的話宜先對 $x$ 和 $y$ 其中一者除以它們的最大公因數 $\gcd(x, y)$ 後兩者再相乘，而且因為除法運算不會有 overflow 問題，它就剛好可以用來檢查乘法結果是否正確。最後是對 0 的特別處理與無限大的代表值，只要小心設計應該就沒問題了。
心得：這題詭異的地方不是這些小細節的設計，而是很多實作看上去是正確的丟上去卻 WA 而無法解釋原因。例如，把第 9 行和第 18 行分別抽換成 leftEP 和 rightEP 的呼叫會在測資點 #8 得到 WA，另外在計算最小公倍數的程式碼如果改成以下 (假設分母可能皆不為兩者的因數的話) d = __gcd(x,y); d0 = __gcd(x,d); x /= d0; d /= d0; d0 = __gcd(y,d); y /= d0; d /= d0; lcm = x * y; 的話也會在測資點 #8 得到 WA。如果有人知道為什麼這兩種實作會導致 WA 的話，歡迎在下方討論區留言或者寄信讓我知道！
1#include <bits/stdc++.h>
2using namespace std;
3
4inline long long rightEP(long long n, unsigned long long m) {
5 if (m == 0) {
6 if (n < 0) return -5e18; // denote -oo
7 return 0;
8 }
9 if (n < 0) return -((-n)/m + ((-n)%m!=0));
10 return n/m;
11}
12
13inline long long leftEP(long long n, unsigned long long m) {
14 if (m == 0) {
15 if (n > 0) return 5e18; // denote +oo
16 return 0;
17 }
18 if (n < 0) return -((-n)/m);
19 return n/m + (n%m!=0);
20}
21
22int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); // IO 優化
23 long long a, b, x, y, lcm, ans=0; cin >> a >> b >> x >> y; x = abs(x), y = abs(y);
24 if (rightEP(b,x) >= leftEP(a,x)) ans += rightEP(b,x) - leftEP(a,x) + 1;
25 if (rightEP(b,y) >= leftEP(a,y)) ans += rightEP(b,y) - leftEP(a,y) + 1;
26 if (!x || !y) lcm = 0;
27 else { // assert(x && y);
28 x /= __gcd(x,y);
29 lcm = x * y;
30 if (lcm/x != y) lcm = 5e18; // check overflow
31 }
32 if (rightEP(b,lcm) >= leftEP(a,lcm)) ans -= rightEP(b,lcm) - leftEP(a,lcm) + 1;
33 cout << ans << '\n';
34 return 0;
35}