Math.cc

#include <algorithm>
#include <vector>

// ******************** EXPONENTS AND POWERS ********************
// Returns value of x raised to y
int power(int x, unsigned int y) {
  int res = 1;
  while (y > 0) {
    if (y & 1) res = res * x;
    y = y >> 1;
    x = x * x;
  }
  return res;
}

// Returns value of (x raised to y) mod p
int power(int x, unsigned int y, int p) {
  int res = 1;
  x = x % p;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}

// ********************** PRIMALITY TESTS **********************
// Returns true if a number is prime
bool isPrime(long long n) {
  if (n == 1)
    return false;
  else if (n < 4)
    return true;
  else
    for (long long t = 2; t * t <= n; t++)
      if (n % t == 0) return false;
  return true;
}

// Returns a sieve where true means prime.
std::vector<bool> sieveOfAtkin(int limit) {
  std::vector<bool> sieve(limit, false);
  sieve[2] = true;
  sieve[3] = true;
  for (int x = 1; x * x < limit; x++) {
    for (int y = 1; y * y < limit; y++) {
      int n = (4 * x * x) + (y * y);
      if (n <= limit && (n % 12 == 1 || n % 12 == 5))
        sieve[n] = sieve[n] ^ true;
      n = (3 * x * x) + (y * y);
      if (n <= limit && n % 12 == 7) sieve[n] = sieve[n] ^ true;
      n = (3 * x * x) - (y * y);
      if (x > y && n <= limit && n % 12 == 11) sieve[n] = sieve[n] ^ true;
    }
  }

  for (int r = 5; r * r < limit; r++) {
    if (sieve[r]) {
      for (int i = r * r; i < limit; i += r * r) sieve[i] = false;
    }
  }
  return sieve;
}

// Returns a list of all prime numbers upto n
std::vector<long long int> primeList(long long int n) {
  std::vector<bool> prime(n + 1, true);
  for (int i = 2; i * i <= n; i++) {
    if (prime[i] == true) {
      for (int j = i * 2; j <= n; j += i) prime[j] = false;
    }
  }
  std::vector<long long int> arr;
  for (int i = 2; i < n; i++)
    if (prime[i]) arr.push_back(i);
  return arr;
}
// ********************* GCD/INVERSE/PRIMEFACTORS *********************

// Returns all the prime factors of a number
std::vector<int> primeFactors(int n) {
  std::vector<int> pfs;
  while (n % 2 == 0) {
    pfs.push_back(2);
    n = n / 2;
  }

  for (int i = 3; i * i <= n; i = i + 2) {
    while (n % i == 0) {
      pfs.push_back(i);
      n = n / i;
    }
  }
  if (n > 2) pfs.push_back(n);
}

// Returns the GCD of two number
int gcd(int a, int b) {
  if (a == 0) return b;
  return gcd(b % a, a);
}

// Returns the extended GCD of two numbers,
// x and y are coefficients of equation
// a*x + b*y = gcd(a,b)
int gcdExtended(int a, int b, int *x, int *y) {
  if (a == 0) {
    *x = 0;
    *y = 1;
    return b;
  }

  int x1, y1;
  int gcd = gcdExtended(b % a, a, &x1, &y1);
  *x = y1 - (b / a) * x1;
  *y = x1;

  return gcd;
}

// -1 no mod inverse
int modInverse(int a, int m) {
  int x, y;
  int g = gcdExtended(a, m, &x, &y);
  if (g != 1)
    return -1;
  else
    return (x % m + m) % m;
}

// ******************** GREEDY ALGORITHMS ********************

int coinCount(std::vector<int> denominations, int sum) {
  std::sort(denominations.rbegin(), denominations.rend());
  int ans = 0;
  for (auto e : denominations) {
    if (sum == 0) break;
    if (e <= sum) {
      ans += sum / e;
      sum = sum % e;
    }
  }
  return ans;
}

auto activitySelect(std::vector<std::pair<int, int>> &ref, int l) {
  sort(ref.begin(), ref.end());
  std::vector<std::pair<int, int>> ans;
  for (auto e : ref) {
    if (e.first > l)
      break;
    else if (ans.empty())
      ans.push_back(e);
    else if (ans[ans.size() - 1].first <= e.second)
      ans.push_back(e);
  }
  return ans;
}

// ********************** NUMBERS RELATED **********************

int countDigits(long long int n) {
  long long int temp = n;
  int c = 0;
  while (temp != 0) {
    temp = temp / 10;
    c++;
  }
  return c;
}
bool isFrugal(long long int n) {
  std::vector<long long int> r = primeList(n);
  long long int t = n;
  long long int s = 0;
  for (int i = 0; i < r.size(); i++) {
    if (t % r[i] == 0) {
      long long int k = 0;
      while (t % r[i] == 0) {
        t = t / r[i];
        k++;
      }
      if (k == 1)
        s = s + countDigits(r[i]);
      else if (k != 1)
        s = s + countDigits(r[i]) + countDigits(k);
    }
  }
  return (countDigits(n) > s && s != 0);
}

// Also called k-Rough
bool isJagged(int n, int k) {
  std::vector<long long> primes = primeList(n);
  long long min_pf = n;
  for (int i = 0; i < primes.size(); i++)
    if (n % primes[i] == 0) min_pf = primes[i];
  return (min_pf >= k);
}

int maxPrimeFactors(int n) {
  int maxPrime = -1;
  while (n % 2 == 0) {
    maxPrime = 2;
    n /= 2;
  }
  for (int i = 3; i < (int)(n * 1 / 2 + 1); i += 2)
    while (n % i == 0) {
      maxPrime = i;
      n /= i;
    }
  if (n > 2) maxPrime = n;
  return (int)(maxPrime);
}
bool isStormer(int n) { return maxPrimeFactors(n * n + 1) >= 2 * n; }