fork download
copy 
  1. #include <bits/stdc++.h>
  2. typedef long long ll;
  3. using namespace std;
  4. using namespace chrono;
  5. using ull = unsigned long long;
  6. void Code_By_Mohamed_Khaled() {
  7.     ios_base::sync_with_stdio(false);
  8.     cin.tie(nullptr);
  9.     cout.tie(nullptr);
  10. #ifndef ONLINE_JUDGE
  11.     freopen("input.txt", "r", stdin);
  12.     freopen("output.txt", "w", stdout);
  13. #endif
  14. }
  15. const ll mod = 1e9 + 7;
  16. ll add(ll a, ll b) { return ((a % mod) + (b % mod)) % mod; }
  17. ll mul(ll a, ll b) { return (__int128(a) * b) % mod; }
  18. ll sub(ll a, ll b) { return ((a % mod) - (b % mod) + mod) % mod; }
  19. ll power(ll a, ll b, ll m) {
  20.     ll res = 1;
  21.     a %= m;
  22.     while (b > 0) {
  23.         if (b & 1) res = (__int128)res * a % m;
  24.         a = (__int128)a * a % m;
  25.         b >>= 1;
  26.     }
  27.     return res;
  28. }
  29. bool is_prime(ll n) {
  30.     if (n < 2) return false;
  31.     for (ll p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {
  32.         if (n == p) return true;
  33.         if (n % p == 0) return false;
  34.     }
  35.     ll r = 0, d = n - 1;
  36.     while ((d & 1) == 0) d >>= 1, r++;
  37.     for (ll a : {2, 3, 5, 7, 11}) {
  38.         if (a >= n) continue;
  39.         ll x = power(a, d, n);
  40.         if (x == 1 || x == n - 1) continue;
  41.         bool ok = false;
  42.         for (ll i = 0; i < r - 1; i++) {
  43.             x = (__int128)x * x % n;
  44.             if (x == n - 1) {
  45.                 ok = true;
  46.                 break;
  47.             }
  48.         }
  49.         if (!ok) return false;
  50.     }
  51.     return true;
  52. }
  53. ll pollards_rho(ll n) {
  54.     if (n % 2 == 0) return 2;
  55.     if (is_prime(n)) return n;
  56.     while (true) {
  57.         ll x = rand() % (n - 2) + 2;
  58.         ll y = x;
  59.         ll c = rand() % (n - 1) + 1;
  60.         ll d = 1;
  61.         while (d == 1) {
  62.             x = (__int128)x * x % n;
  63.             x = (x + c) % n;
  64.             y = (__int128)y * y % n;
  65.             y = (y + c) % n;
  66.             y = (__int128)y * y % n;
  67.             y = (y + c) % n;
  68.             d = __gcd(abs(x - y), n);
  69.         }
  70.         if (d != n) return d;
  71.     }
  72. }
  73. void pollard_fact(ll n, map<ll,ll>&mp) {
  74.     if (n == 1) return;
  75.     if (is_prime(n)) {
  76.         mp[n]++;
  77.         return;
  78.     }
  79.     ll f = pollards_rho(n);
  80.     pollard_fact(f, mp);
  81.     pollard_fact(n / f, mp);
  82. }
  83. ll cnt_pairs(ll k) {
  84.     map<ll,ll>mp;
  85.     pollard_fact(k,mp);
  86.     return 1LL<<mp.size();
  87. }
  88. vector<ll> get_divisors(ll n) {
  89.     vector<ll> div;
  90.     for (ll b = 1; b * b <= n; b++) {
  91.         if (n % b == 0) {
  92.             div.push_back(b);
  93.             if (b * b != n) div.push_back(n / b);
  94.         }
  95.     }
  96.     return div;
  97. }
  98. int main() {
  99. 	auto start = high_resolution_clock::now();
  100.     Code_By_Mohamed_Khaled();
  101.     // srand(time(0));
  102.     ll t=1;
  103.     while(t--){
  104. 	    ll c,d,x;
  105. 	    cin>>c>>d>>x;
  106. 	    vector<ll>div=get_divisors(x);
  107. 	    ll ans=0;
  108. 	    for (auto it:div) {
  109. 	        ll g=it,k=x/g+d;
  110. 	        if (k%c) continue;
  111. 	        k/=c;
  112. 	        ans+=cnt_pairs(k);
  113. 	    }
  114. 	    cout<<ans<<"\n";
  115.     }
  116.     auto end = high_resolution_clock::now();
  117.     auto duration = duration_cast<microseconds>(end - start);
  118.     cout << "Time taken: " << duration.count() << " microseconds" << endl;
  119.     return 0;
  120. }
  121.  
Success #stdin #stdout 1.37s 5284KB
comments (?)
stdin
copy 
1 1 9999999999991577
stdout
copy 
106
Time taken: 1379494 microseconds
https://ideone.com/2I9FaL
language:
C++ (gcc 8.3)
created:
23 hours 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!