SHARE
TWEET

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

ahmed_aly Apr 13th, 2011 1,270 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. int main() {
  52.         int a, b, n;
  53.         scanf("%d", &a);
  54.         getFactors(a);
  55.         getDivisors();
  56.         vector<int> d1 = divisors;
  57.         scanf("%d", &b);
  58.         getFactors(b);
  59.         divisors.clear();
  60.         getDivisors();
  61.         vector<int> d2 = divisors;
  62.         sort(d1.begin(), d1.end());
  63.         sort(d2.begin(), d2.end());
  64.         vector<int> cd;
  65.         set_intersection(d1.begin(), d1.end(), d2.begin(), d2.end(), inserter(cd,
  66.                         cd.begin()));
  67.         scanf("%d", &n);
  68.         int low, high, ind;
  69.         for (int i = 0; i < n; i++) {
  70.                 scanf("%d%d", &low, &high);
  71.                 ind = upper_bound(cd.begin(), cd.end(), high) - cd.begin();
  72.                 ind--;
  73.                 if (ind == -1 || cd[ind] < low)
  74.                         printf("-1\n");
  75.                 else
  76.                         printf("%d\n", cd[ind]);
  77.         }
  78.         return 0;
  79. }
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