Advertisement
ahmed_aly

Java solution for problem C (with binary search)

Apr 13th, 2011
1,097
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.68 KB | None | 0 0
  1. import java.io.BufferedReader;
  2. import java.io.BufferedWriter;
  3. import java.io.InputStreamReader;
  4. import java.io.OutputStreamWriter;
  5. import java.io.PrintWriter;
  6. import java.util.Collections;
  7. import java.util.Scanner;
  8. import java.util.Vector;
  9.  
  10. public class modified_gcd_ahmed_java_ac {
  11.  
  12.     static Vector<Integer> v1, v2;
  13.  
  14.     static void getFactors(int n) {
  15.         v1 = new Vector<Integer>();
  16.         v2 = new Vector<Integer>();
  17.         int d = 1, temp;
  18.         for (int i = 2; i * i <= n; i += d, d = 2)
  19.             if (n % i == 0) {
  20.                 v1.add(i);
  21.                 temp = 0;
  22.                 while (n % i == 0) {
  23.                     n /= i;
  24.                     temp++;
  25.                 }
  26.                 v2.add(temp);
  27.             }
  28.         if (n != 1) {
  29.             v1.add(n);
  30.             v2.add(1);
  31.         }
  32.     }
  33.  
  34.     static Vector<Integer> divisors;
  35.  
  36.     static void getDivisors(int ind, int res) {
  37.         if (ind == (int) v1.size()) {
  38.             divisors.add(res);
  39.             return;
  40.         }
  41.         for (int i = 0; i <= v2.get(ind); i++) {
  42.             getDivisors(ind + 1, res);
  43.             res *= v1.get(ind);
  44.         }
  45.     }
  46.  
  47.     static Vector<Integer> getCDs(int a, int b) {
  48.         getFactors(a);
  49.         divisors = new Vector<Integer>();
  50.         getDivisors(0, 1);
  51.         Vector<Integer> d1 = divisors;
  52.         getFactors(b);
  53.         divisors = new Vector<Integer>();
  54.         getDivisors(0, 1);
  55.         Vector<Integer> d2 = divisors;
  56.         Collections.sort(d1);
  57.         Collections.sort(d2);
  58.         Vector<Integer> cd = new Vector<Integer>();
  59.         int i1 = 0, i2 = 0;
  60.         while (i1 < d1.size() && i2 < d2.size()) {
  61.             if (d1.get(i1).compareTo(d2.get(i2)) == 0) {
  62.                 cd.add(d1.get(i1));
  63.                 i1++;
  64.                 i2++;
  65.             } else if (d1.get(i1).compareTo(d2.get(i2)) < 0)
  66.                 i1++;
  67.             else
  68.                 i2++;
  69.         }
  70.         return cd;
  71.     }
  72.  
  73.     static int upper_bound(Vector<Integer> v, int x) {
  74.         int st = 0, en = v.size();
  75.         while (st < en) {
  76.             int md = (st + en) / 2;
  77.             if (v.get(md) > x)
  78.                 en = md;
  79.             else
  80.                 st = md + 1;
  81.         }
  82.         return st;
  83.     }
  84.  
  85.     static void print(Vector<Integer> v) {
  86.         System.out.print("{");
  87.         for (int i = 0; i < v.size(); i++) {
  88.             if (i > 0)
  89.                 System.out.print(", ");
  90.             System.out.print(v.get(i));
  91.         }
  92.         System.out.println("}");
  93.     }
  94.  
  95.     public static void main(String[] args) {
  96.         BufferedReader bfin = new BufferedReader(new InputStreamReader(
  97.                 System.in));
  98.         BufferedWriter bfout = new BufferedWriter(new OutputStreamWriter(
  99.                 System.out));
  100.         Scanner cin = new Scanner(bfin);
  101.         PrintWriter cout = new PrintWriter(bfout);
  102.         int a, b, n;
  103.         a = cin.nextInt();
  104.         b = cin.nextInt();
  105.         Vector<Integer> cd = getCDs(a, b);
  106.         n = cin.nextInt();
  107.         int low, high, ind;
  108.         for (int i = 0; i < n; i++) {
  109.             low = cin.nextInt();
  110.             high = cin.nextInt();
  111.             ind = upper_bound(cd, high);
  112.             ind--;
  113.             if (ind == -1 || cd.get(ind) < low)
  114.                 cout.println(-1);
  115.             else
  116.                 cout.println(cd.get(ind));
  117.         }
  118.         cout.close();
  119.     }
  120. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement