SHARE
TWEET

C++ solution for problem C (without binary search)

ahmed_aly Apr 13th, 2011 893 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <cstring>
  2. #include <map>
  3. #include <deque>
  4. #include <queue>
  5. #include <stack>
  6. #include <sstream>
  7. #include <iostream>
  8. #include <iomanip>
  9. #include <cstdio>
  10. #include <cmath>
  11. #include <cstdlib>
  12. #include <ctime>
  13. #include <algorithm>
  14. #include <vector>
  15. #include <set>
  16. #include <complex>
  17. #include <list>
  18. #include <climits>
  19. #include <cctype>
  20.  
  21. using namespace std;
  22.  
  23. vector<pair<int, int> > factors;
  24. void getFactors(int n) {
  25.         factors.clear();
  26.         int d = 1;
  27.         for (int i = 2; i * i <= n; i += d, d = 2)
  28.                 if (n % i == 0) {
  29.                         factors.push_back(make_pair(i, 0));
  30.                         while (n % i == 0) {
  31.                                 n /= i;
  32.                                 factors.back().second++;
  33.                         }
  34.                 }
  35.         if (n != 1)
  36.                 factors.push_back(make_pair(n, 1));
  37. }
  38.  
  39. vector<int> divisors;
  40. void getDivisors(int ind = 0, int res = 1) {
  41.         if (ind == (int) factors.size()) {
  42.                 divisors.push_back(res);
  43.                 return;
  44.         }
  45.         for (int i = 0; i <= factors[ind].second; i++) {
  46.                 getDivisors(ind + 1, res);
  47.                 res *= factors[ind].first;
  48.         }
  49. }
  50.  
  51. vector<int> getCDs(int a, int b) {
  52.         getFactors(a);
  53.         divisors.clear();
  54.         getDivisors();
  55.         vector<int> d1 = divisors;
  56.         getFactors(b);
  57.         divisors.clear();
  58.         getDivisors();
  59.         vector<int> d2 = divisors;
  60.         sort(d1.begin(), d1.end());
  61.         sort(d2.begin(), d2.end());
  62.         vector<int> cd;
  63.         set_intersection(d1.begin(), d1.end(), d2.begin(), d2.end(), inserter(cd,
  64.                         cd.begin()));
  65.         return cd;
  66. }
  67.  
  68. int main() {
  69.         int a, b, n;
  70.         scanf("%d%d", &a, &b);
  71.         vector<int> cd = getCDs(a, b);
  72.         scanf("%d", &n);
  73.         int low, high, ind;
  74.         for (int i = 0; i < n; i++) {
  75.                 scanf("%d%d", &low, &high);
  76.                 ind = -1;
  77.                 for (int j = ((int) cd.size()) - 1; j >= 0; j--)
  78.                         if (cd[j] >= low && cd[j] <= high) {
  79.                                 ind = j;
  80.                                 break;
  81.                         }
  82.                 if (ind == -1)
  83.                         printf("-1\n");
  84.                 else
  85.                         printf("%d\n", cd[ind]);
  86.         }
  87.         return 0;
  88. }
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