Codeforces Beta Round #67 (Div. 2) Problem C

Link: C. Modified GCD

This is my solution.

int main(){
    int a, b, n, x, y;
    scanf("%d %d %d", &a, &b, &n);
    int d = __gcd(a, b);
    set<int> v;
    v.insert(d);
    for(int i=1; i <= sqrt(d) ;i++){
        if(d%i == 0){
            v.insert(i);
            v.insert(d/i);
        }
    }
    vector<int> val(v.begin(), v.end());
    for(int i=0; i<n ;i++){
        scanf("%d %d", &x, &y);
        a = 0, b = val.size()-1;
        while(a != b){
            int mid = ((a+b)/2)+1;
            if(val[mid] > y) b = mid-1;
            else a = mid;
        }
        int r=-1;
        if(a+1 < val.size()){
            if(val[a+1] <= y && val[a+1] >= x)
                r = val[a+1];
        }
        if(val[a] <= y && val[a] >= x)
            r = max(val[a], r);
        if(a-1 >= 0){
            if(val[a-1] <= y && val[a-1] >= x)
                r = max(r, val[a-1]);
        }
        printf("%dn", r);
    }
}

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión /  Cambiar )

Google photo

Estás comentando usando tu cuenta de Google. Cerrar sesión /  Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión /  Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión /  Cambiar )

Conectando a %s