Beta Round #67-D: Modified GCD

解法

約数は最大公約数の約数になっている。約数の個数なんてたかが知れているので全探索で十分間に合う。間に合うときは変に2分探索とかしない。

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

int A, B;
int L, H;
vector<int> ds;

void init(){
	int D = __gcd(A,B);
	for(int i=1; i*i<=D; i++){
		if(D%i==0){
			ds.push_back(D/i);
			ds.push_back(i);
		}
	}
	sort(ds.begin(), ds.end());
	ds.erase(unique(ds.begin(), ds.end()), ds.end());
}

int solve(){
	int ans = -1;
	for(int i=0; i<ds.size(); i++){
		if(L<=ds[i] && ds[i]<=H){
			ans = ds[i];
		}
	}
	return ans;
}

int main(){
	scanf("%d%d",&A,&B);
	init();
	int N;
	scanf("%d",&N);
	for(int i=0; i<N; i++){
		scanf("%d%d",&L,&H);
		printf("%d\n",solve());
	}
	return 0;
}