【CodeForces】75C - Modified GCD（快速求公约数，upper_bound函数）

C. Modified GCD

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Well, here is another math class task. In mathematics, GCD is the greatest common divisor, and it's an easy task to calculate the GCD between two positive integers.

A common divisor for two positive numbers is a number which both numbers are divisible by.

But your teacher wants to give you a harder task, in this task you have to find the greatest common divisor d between two integers a andb that is in a given range from low to high (inclusive), i.e. low ≤ d ≤ high. It is possible that there is no common divisor in the given range.

You will be given the two integers a and b, then n queries. Each query is a range from low to high and you have to answer each query.

Input

The first line contains two integers a and b, the two integers as described above (1 ≤ a, b ≤ 109). The second line contains one integern, the number of queries (1 ≤ n ≤ 104). Then n lines follow, each line contains one query consisting of two integers, low and high(1 ≤ low ≤ high ≤ 109).

Output

Print n lines. The i-th of them should contain the result of the i-th query in the input. If there is no common divisor in the given range for any query, you should print -1 as a result for this query.

Examples

input

9 27
3
1 5
10 11
9 11

output

3
-1
9

这里有一个快速求所有公约数的方法：

先求出 GCD(a , b ) = g；

然后找g的约数即可，（从1到sqrt（g）枚举）。

排序后用upper_bound()函数找出小于 r 的最大的值，然后与 l 比较即可。

代码如下：

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;
int c[100000];
int GCD(int a,int b)
{
	if (a % b == 0)
		return b;
	return GCD(b , a % b);
}
int main()
{
	int a,b;
	int num = 0;
	scanf ("%d %d",&a,&b);
	int g = GCD (a,b);
	int l = sqrt ((double)g);
	for (int i = 1 ; i <= l ; i++)
	{
		if (g % i == 0)
		{
			c[num++] = i;
			c[num++] = g / i;
		}
	}
	sort (c , c + num);
	int m;		//查询次数 
	scanf ("%d",&m);
	while (m--)
	{
		int l,r;
		scanf ("%d %d",&l,&r);
		int t = upper_bound(c , c + num , r) - c - 1;
		//返回的是大于它的地址，首先把这个地址减一，然后减去首地址得到下标 
		if (c[t] < l)
			printf ("-1\n");
		else
			printf ("%d\n",c[t]);
	}
	return 0;
}