Codeforces 1513D - GCD and MST(設計解題)

解法

由於我們要使 GCD 最大，因此必須使 n 都要是 x 的倍數，所以只需要判斷 x 可以被哪個因數整除，在判斷是否有大於 n，若有，則可以用 x / 因數 方式來解決；反之概念相同。

程式碼

#include <iostream>
#include <bits/stdc++.h>
#define LOCAL
#define MAXN 0x3f3f3f
using namespace std;
int t, x, n;

int process(){
    int ans = 0;
    for(int i = 1; i * i <= x; i++){
        if(x % i == 0){
            //cout << "hi " << i << "\n";
            if(i >= n) ans = max(ans, x/i);
            if(x/i >= n) ans = max(ans, i);
        }
    }
    return ans;
}

int main()
{
#ifdef LOCAL
    freopen("in1.txt", "r", stdin);
#endif // LOCAL
    cin >> t;
    while(t--){
        cin >> x >> n;
        cout << process() << "\n";
    }

    return 0;
}