SHARE
TWEET

Java solution for problem C (with binary search)

ahmed_aly Apr 13th, 2011 380 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top