fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define  ll long long
  4. #define  ul unsigned long long
  5. using db = long double;
  6. #pragma GCC optimize("Ofast")
  7. #pragma GCC target("avx,avx2,fma")
  8. void Code_By_Mohamed_Khaled() {
  9.     ios_base::sync_with_stdio(false);
  10.     cin.tie(nullptr);
  11. #ifndef ONLINE_JUDGE
  12.     freopen("input.txt", "r", stdin);
  13.     freopen("output.txt", "w", stdout);
  14. #endif
  15. }
  16. class Pollard {
  17. public:
  18.     map<ul, int> cnt_primes;
  19.     vector<ul> primes, divisors;
  20.     ul modMul(ul a, ul b, const ul mod) {
  21.         ll ret = a * b - mod * (ul)((db)a * b / mod);
  22.         return ret + ((ret < 0) - (ret >= (ll)mod)) * mod;
  23.     }
  24.     ul modPow(ul a, ul b, const ul mod) {
  25.         if (b == 0) return 1;
  26.         ul res = modPow(a, b / 2, mod);
  27.         res = modMul(res, res, mod);
  28.         return b & 1 ? modMul(res, a, mod) : res;
  29.     }
  30.  
  31.     bool rabin_miller(ul n) {  // not ll!
  32.         if (n < 2 || n % 6 % 4 != 1) return n - 2 < 2;
  33.         ul A[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
  34.                 s = __builtin_ctzll(n - 1), d = n >> s;
  35.         for (auto a : A) {  // ^ count trailing zeroes
  36.             ul p = modPow(a, d, n), i = s;
  37.             while (p != 1 && p != n - 1 && a % n && i--) p = modMul(p, p, n);
  38.             if (p != n - 1 && i != s) return 0;
  39.         }
  40.         return 1;
  41.     }
  42.     ul pollard(ul n) {  // return some nontrivial factor of n
  43.         auto f = [n, this](ul x) { return modMul(x, x, n) + 1; };
  44.         ul x = 0, y = 0, t = 30, prd = 2, i = 1, q;
  45.         while (t++ % 40 ||
  46.                __gcd(prd, n) == 1) {  /// speedup: don't take gcd every it
  47.             if (x == y) x = ++i, y = f(x);
  48.             if ((q = modMul(prd, max(x, y) - min(x, y), n))) prd = q;
  49.             x = f(x), y = f(f(y));
  50.         }
  51.         return __gcd(prd, n);
  52.     }
  53.     void factor_rec(ul n, map<ul, int> &cnt) {
  54.         if (n == 1) return;
  55.         if (rabin_miller(n)) {
  56.             ++cnt[n];
  57.             return;
  58.         }
  59.         ul u = pollard(n);
  60.         factor_rec(u, cnt), factor_rec(n / u, cnt);
  61.     }
  62.     void calcDivisorsRec(ul cur, int i) {
  63.         if (i >= primes.size()) {
  64.             divisors.push_back(cur);
  65.             return;
  66.         }
  67.         int r = cnt_primes[primes[i]];
  68.         for (int j = 0; j <= r; j++) {
  69.             calcDivisorsRec(cur, i + 1);
  70.             cur = cur * primes[i];
  71.         }
  72.     }
  73.     void calcDivisors(ul x) {
  74.         cnt_primes.clear();
  75.         primes.clear();
  76.         divisors.clear();
  77.         factor_rec(x, cnt_primes);
  78.         for (auto &u : cnt_primes) {
  79.             primes.push_back(u.first);
  80.         }
  81.         calcDivisorsRec(1, 0);
  82.     }
  83. } pollard;
  84. int main() {
  85. 	Code_By_Mohamed_Khaled();
  86. 	int t;cin>>t;
  87. 	while(t--)
  88. 	{
  89. 		ll a,b;cin>>a>>b;
  90. 		pollard.calcDivisors(a*b);
  91. 		auto all=pollard.divisors;
  92. 		int ans=0;
  93. 		for(ll j=0;j<all.size();j++)
  94. 		{
  95. 			ll i=all[j];
  96. 			ll y=a-i;
  97. 			ll x=a*b/(a-y)-b;
  98. 			if(x>0)ans++;
  99. 		}
  100. 		cout<<ans<<"\n";
  101. 	}
  102. 	return 0;
  103. }
Success #stdin #stdout 0s 5324KB
comments (?)
stdin 
3
4 10
5 7
7 9
stdout 
2
1
2
https://ideone.com/VQPzhs
language:
C++ (gcc 8.3)
created:
8 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!