CodeForces 75C Modified GCD [二分+數論]

先求出a和b的最大公約數，找出其所有的因數——sqrt(n)的復雜度，漲姿勢了。

然後就是判斷所有的因數有沒有落在low,high區間裡面了——二分即可（upper_bound）

C++版本：

[cpp] #include <cstdio>  
#include <cstring>  
#include <iostream>  
#include <algorithm>  
#include <cmath>  
#include <vector>  
using namespace std; 
typedef long long ll; 
vector<int> x; 
int low, high, a, b, n, m, ans; 
 
int main() { 
    scanf("%d%d", &a, &b); 
    a = __gcd(a, b); 
    b = sqrt(a); 
    x.clear(); 
    for (int i=1; i<=b; i++) 
        if (a % i == 0) { 
            x.push_back(i); 
            x.push_back(a/i); 
        } 
    sort(x.begin(), x.end()); 
    scanf("%d", &n); 
    for (int i=0; i<n; i++) { 
        scanf("%d%d", &low, &high); 
        m = upper_bound(x.begin(), x.end(), high) - x.begin() - 1; 
        ans = x[m]; 
        if (low > ans) puts("-1"); 
        else printf("%d\n", ans); 
    } 
 
    return 0; 
} 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
typedef long long ll;
vector<int> x;
int low, high, a, b, n, m, ans;

int main() {
    scanf("%d%d", &a, &b);
    a = __gcd(a, b);
    b = sqrt(a);
    x.clear();
    for (int i=1; i<=b; i++)
        if (a % i == 0) {
            x.push_back(i);
            x.push_back(a/i);
        }
    sort(x.begin(), x.end());
    scanf("%d", &n);
    for (int i=0; i<n; i++) {
        scanf("%d%d", &low, &high);
        m = upper_bound(x.begin(), x.end(), high) - x.begin() - 1;
        ans = x[m];
        if (low > ans) puts("-1");
        else printf("%d\n", ans);
    }

    return 0;
}

Python版本：

[python]  from fractions import gcd 
from bisect import bisect_right as br  
g = gcd(*map(int, raw_input().split())) 
i = 1 
r = [] 
while i*i <= g: 
    if g % i == 0: 
        r.append(i) 
        r.append(g/i) 
    i += 1 
r = sorted(r) 
 
for i in xrange(input()): 
    l, h = map(int, raw_input().split()) 
    m = r[br(r, h)-1] 
    print -1 if m < l else m 
 
     

from fractions import gcd
from bisect import bisect_right as br
g = gcd(*map(int, raw_input().split()))
i = 1
r = []
while i*i <= g:
    if g % i == 0:
        r.append(i)
        r.append(g/i)
    i += 1
r = sorted(r)

for i in xrange(input()):
    l, h = map(int, raw_input().split())
    m = r[br(r, h)-1]
    print -1 if m < l else m