C. Modified GCD
time limit per test 2 seconds
memory limit per test 256 megabytes
题目连接: 传送门
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 divisord between two integers a and b that is in a given range fromlow 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 tohigh 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). Thenn lines follow, each line contains one query consisting of two integers,low and high (1?≤?low?≤?high?≤?109).
Output
Print n lines. Thei-th of them should contain the result of thei-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.
Sample test(s) Input
9 27
3
1 5
10 11
9 11
Output
3
-1
9
AC代码:
#include
#include
#include
using namespace std; const int M = 1e6; int ma[M]; int Gcd(int a, int b) { return b == 0 ? a : Gcd(b, a % b); } int main() { int a,b,n,ua,ub; while(~scanf("%d %d",&a,&b)) { scanf("%d",&n); int ans = Gcd(a,b), to = 0; for(int i = 1; i * i <= ans; i++) //运用求素数的方法sqrt时间复杂度找出所有约数; { if(ans % i == 0) { ma[to++] = i; if(i * i != ans) ma[to++] = ans / i; } } sort(ma,ma + to); while(n--) { scanf("%d %d",&ua,&ub); int tp = lower_bound(ma, ma + to, ub) - ma; if(ma[tp] > ub || tp == to) tp--; if(ma[tp] < ua || ma[tp] > ub) puts("-1"); else printf("%d\n",ma[tp]); } } return 0; }