BZOJ 3834: Poi 2014 Solar Panels - 數論 GCD 區間查詢

問題描述

給定 a,b,c,d，多次查詢：x∈[a,b], y∈[c,d] 時，gcd(x,y) 的最大可能值。

核心觀察

枚舉 g = gcd(x,y)。區間 [a,b] 含 g 的倍數 ⇔ ⌊b/g⌋ > ⌊(a-1)/g⌋。同理 [c,d]。
商 ⌊b/g⌋ 只有 O(√b) 種取值。枚舉商值區間，在 O(√max(b,d)) 內找到最大合法 g。

代碼

int main() {
    int T; cin >> T;
    while (T--) {
        int a,b,c,d; cin >> a >> b >> c >> d;
        int ans = 1;
        for (int i = 1, last; i <= b && i <= d; i = last + 1) {
            last = min(b/(b/i), d/(d/i));
            if (b/last > (a-1)/last && d/last > (c-1)/last)
                ans = max(ans, last);
        }
        cout << ans << '\n';
    }
}