Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- import java.io.BufferedReader;
- import java.io.BufferedWriter;
- import java.io.InputStreamReader;
- import java.io.OutputStreamWriter;
- import java.io.PrintWriter;
- import java.util.Collections;
- import java.util.Scanner;
- import java.util.Vector;
- public class modified_gcd_ahmed_java_ac {
- static Vector<Integer> v1, v2;
- static void getFactors(int n) {
- v1 = new Vector<Integer>();
- v2 = new Vector<Integer>();
- int d = 1, temp;
- for (int i = 2; i * i <= n; i += d, d = 2)
- if (n % i == 0) {
- v1.add(i);
- temp = 0;
- while (n % i == 0) {
- n /= i;
- temp++;
- }
- v2.add(temp);
- }
- if (n != 1) {
- v1.add(n);
- v2.add(1);
- }
- }
- static Vector<Integer> divisors;
- static void getDivisors(int ind, int res) {
- if (ind == (int) v1.size()) {
- divisors.add(res);
- return;
- }
- for (int i = 0; i <= v2.get(ind); i++) {
- getDivisors(ind + 1, res);
- res *= v1.get(ind);
- }
- }
- static Vector<Integer> getCDs(int a, int b) {
- getFactors(a);
- divisors = new Vector<Integer>();
- getDivisors(0, 1);
- Vector<Integer> d1 = divisors;
- getFactors(b);
- divisors = new Vector<Integer>();
- getDivisors(0, 1);
- Vector<Integer> d2 = divisors;
- Collections.sort(d1);
- Collections.sort(d2);
- Vector<Integer> cd = new Vector<Integer>();
- int i1 = 0, i2 = 0;
- while (i1 < d1.size() && i2 < d2.size()) {
- if (d1.get(i1).compareTo(d2.get(i2)) == 0) {
- cd.add(d1.get(i1));
- i1++;
- i2++;
- } else if (d1.get(i1).compareTo(d2.get(i2)) < 0)
- i1++;
- else
- i2++;
- }
- return cd;
- }
- static int upper_bound(Vector<Integer> v, int x) {
- int st = 0, en = v.size();
- while (st < en) {
- int md = (st + en) / 2;
- if (v.get(md) > x)
- en = md;
- else
- st = md + 1;
- }
- return st;
- }
- static void print(Vector<Integer> v) {
- System.out.print("{");
- for (int i = 0; i < v.size(); i++) {
- if (i > 0)
- System.out.print(", ");
- System.out.print(v.get(i));
- }
- System.out.println("}");
- }
- public static void main(String[] args) {
- BufferedReader bfin = new BufferedReader(new InputStreamReader(
- System.in));
- BufferedWriter bfout = new BufferedWriter(new OutputStreamWriter(
- System.out));
- Scanner cin = new Scanner(bfin);
- PrintWriter cout = new PrintWriter(bfout);
- int a, b, n;
- a = cin.nextInt();
- b = cin.nextInt();
- Vector<Integer> cd = getCDs(a, b);
- n = cin.nextInt();
- int low, high, ind;
- for (int i = 0; i < n; i++) {
- low = cin.nextInt();
- high = cin.nextInt();
- ind = upper_bound(cd, high);
- ind--;
- if (ind == -1 || cd.get(ind) < low)
- cout.println(-1);
- else
- cout.println(cd.get(ind));
- }
- cout.close();
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement