Advertisement
ahmed_aly

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

Apr 13th, 2011
3,582
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.76 KB | None | 0 0
  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. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement