Number Theory Basics

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

bool isPrime(ll n) {
    if (n < 2) return false;
    if (n < 4) return true;
    if (n % 2 == 0 || n % 3 == 0) return false;
    for (ll i = 5; i * i <= n; i += 6)
        if (n % i == 0 || n % (i + 2) == 0) return false;
    return true;
}

vector<ll> primeFactorization(ll n) {
    vector<ll> factors;
    while (n % 2 == 0) { factors.push_back(2); n /= 2; }
    for (ll i = 3; i * i <= n; i += 2)
        while (n % i == 0) { factors.push_back(i); n /= i; }
    if (n > 1) factors.push_back(n);
    return factors;
}

ll totient(ll n) {
    ll result = n;
    for (ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            while (n % i == 0) n /= i;
            result -= result / i;
        }
    }
    if (n > 1) result -= result / n;
    return result;
}

vector<ll> divisors(ll n) {
    vector<ll> divs;
    for (ll i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divs.push_back(i);
            if (i != n / i) divs.push_back(n / i);
        }
    }
    return divs;
}

int countDivisors(ll n) {
    int cnt = 0;
    for (ll i = 1; i * i <= n; i++)
        if (n % i == 0) { cnt += 2; if (i == n / i) cnt--; }
    return cnt;
}

ll sumDivisors(ll n) {
    ll sum = 0;
    for (ll i = 1; i * i <= n; i++)
        if (n % i == 0) { sum += i; if (i != n / i) sum += n / i; }
    return sum;
}

ll isqrt(ll n) {
    ll s = (ll)sqrt((double)n);
    while (s > 0 && s * s > n) s--;
    while ((s + 1) * (s + 1) <= n) s++;
    return s;
}

bool isPerfectSquare(ll n) {
    if (n < 0) return false;
    ll s = isqrt(n);
    return s * s == n;
}

bool isPerfectPower(ll n, int base) {
    if (n <= 0) return false;
    if (n == 1) return true;
    ll p = 1;
    while (p < n) {
        p *= base;
        if (p == n) return true;
        if (p > n / base) break;
    }
    return false;
}