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; }