Untitled

/// Pollards Rho G4G - O(sqrt(N) * log(N))
/// complexidade segundo o ChatGPT - O(N ^ (1/4))

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

/* Function to calculate (base^exponent)%modulus */
ll modular_pow(ll base, int exponent, ll modulus) {
  ll result = 1;

  while (exponent > 0) {
    if (exponent & 1)
      result = (result * base) % modulus;

    exponent = exponent >> 1;

    base = (base * base) % modulus;
  }

  return result;
}

ll PollardRho(ll n) {
  srand(time(NULL));

  if (n == 1) return n;
  if (n % 2 == 0) return 2;

  ll x = (rand() % (n - 2)) + 2;
  ll y = x;
  ll c = (rand() % (n - 1)) + 1;
  ll d = 1;

  while (d == 1) {
    x = (modular_pow(x, 2, n) + c + n) % n;
    y = (modular_pow(y, 2, n) + c + n) % n;
    y = (modular_pow(y, 2, n) + c + n) % n;
    d = __gcd(abs(x - y), n);

    if (d == n) return PollardRho(n);
  }

  return d;
}

int main() {
  ios_base::sync_with_stdio(0), cin.tie(nullptr);

  ll n = 10967535067;
  cout<<"One of the divisors for "<<n<<" is "<<PollardRho(n)<<'\n';
}