Advertisement
MathQ_

Untitled

Jul 6th, 2021
122
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 3.54 KB | None | 0 0
  1. #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
  2. #pragma GCC optimize 03
  3. #pragma GCC optimize("unroll-loops")
  4.  
  5. #include <iostream>
  6. #include <iomanip>
  7. #include <algorithm>
  8. #include <iterator>
  9. #include <cmath>
  10. #include <ctime>
  11. #include <vector>
  12. #include <deque>
  13. #include <queue>
  14. #include <set>
  15. #include <map>
  16. #include <stack>
  17. #include <string>
  18. #include <random>
  19. #include <numeric>
  20. #include <unordered_set>
  21. #include <unordered_map>
  22. #include <ext/pb_ds/assoc_container.hpp>
  23. #include <ext/pb_ds/tree_policy.hpp>
  24.  
  25. using namespace std;
  26. using namespace __gnu_pbds;
  27.  
  28. typedef std::pair<int, int> pii;
  29. typedef std::pair<char, char> pcc;
  30. typedef std::pair<short, char> psc;
  31. typedef unsigned long long ull;
  32. typedef long long ll;
  33. typedef long double lb;
  34. typedef tree<int,
  35.              null_type,
  36.              less<int>,
  37.              rb_tree_tag,
  38.              tree_order_statistics_node_update> ordered_set;
  39.  
  40. #define fast ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
  41. #define file_in freopen("input.txt", "r", stdin);
  42. #define file_in_out freopen("commander.in", "r", stdin); freopen("commander.out", "w", stdout);
  43. #define all(x) (x).begin(), (x).end()
  44. #define fi first
  45. #define se second
  46.  
  47. template<typename T>
  48. istream& operator>>(istream &in, vector<T> &v) {
  49.     for (auto &it : v) {
  50.         in >> it;
  51.     }
  52.     return in;
  53. }
  54.  
  55. template<typename T>
  56. ostream& operator<<(ostream &out, const vector<T> &v) {
  57.     for (auto &it : v) {
  58.         out << it << " ";
  59.     }
  60.     return out;
  61. }
  62.  
  63. template<typename T1, typename T2>
  64. istream& operator>>(istream &in, pair<T1, T2> &v) {
  65.     in >> v.fi >> v.se;
  66.     return in;
  67. }
  68.  
  69. template<typename T1, typename T2>
  70. ostream& operator<<(ostream &out, const pair<T1, T2> &v) {
  71.     out << v.fi << " " << v.se;
  72.     return out;
  73. }
  74.  
  75. int ans = 0;
  76. ll l, r, x, y;
  77. bool not_overflow(lb a, lb b) {
  78.     return a <= (1ll << 62) / b;
  79. }
  80. map<pair<ll, ll>, char> used;
  81. void rec(int i, ll p, vector<vector<ll>> pp) {
  82.     if (i == pp.size()) {
  83.         if (l <= p && p <= r && l <= x * y / p && x * y / p <= r && gcd(p, x * y / p) == x && lcm(p, x * y / p) == y && !used[{p, x * y / p}]) {
  84.             used[{p, x * y / p}] = 1;
  85.             ++ans;
  86.         }
  87.         return;
  88.     }
  89.     for (auto el : pp[i]) {
  90.         if (not_overflow(p, el)) rec(i + 1, p * el, pp);
  91.     }
  92. }
  93.  
  94. int main() {
  95.     fast
  96.     // file_in
  97.     // file_in_out
  98.    
  99.     cin >> l >> r >> x >> y;
  100.     ll xx = x, yy = y;
  101.     map<int, int> divs1, divs2;
  102.     for (int i = 2; i * i <= xx; ++i) {
  103.         int c = 0;
  104.         while (xx % i == 0) { ++c; xx /= i; }
  105.         divs1[i] = c;
  106.     }
  107.     for (int i = 2; i * i <= yy; ++i) {
  108.         int c = 0;
  109.         while (yy % i == 0) { ++c; yy /= i; }
  110.         divs2[i] = c;
  111.     }
  112.     divs1[xx] = (xx != 1); divs2[yy] = (yy != 1);
  113.     for (auto [d, c] : divs1) {
  114.         divs1[d] += divs2[d];
  115.         divs2[d] = 0;
  116.     }
  117.     vector<pii> div;
  118.     for (auto el : divs1) if (el.se != 0) div.push_back(el);
  119.     for (auto el : divs2) if (el.se != 0) div.push_back(el);
  120.     int n = div.size();
  121.  
  122.     for (int i = 0; i < (1 << n); ++i) {
  123.         int j = i, k = 0;
  124.         vector<vector<ll>> pp;
  125.         while (j) {
  126.             if (j & 1) {
  127.                 vector<ll> now;
  128.                 ll st = div[k].fi;
  129.                 for (int s = 0; s < div[k].se; ++s) { now.push_back(st); st *= div[k].fi; }
  130.                 pp.push_back(now);
  131.             }
  132.             j >>= 1;
  133.             ++k;
  134.         }
  135.         rec(0, 1, pp);
  136.     }
  137.     cout << ans << '\n';
  138.     return 0;
  139. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement