Pollard Rho (Factoring algorithm)

factor.h

ull f(ull x, ull n) { return (mod_mul(x, x, n) + 1) % n; }
ull Pollard(ull n) {
	if (isPrime(n)) return n;
	if (!(n & 1)) return 2;
	for(int i = 1; i < 50; i++) {
		ull x = i, y = f(x, n), p = __gcd(n + y - x, n);
		while (p == 1)
			x = f(x, n), y = f(f(y, n), n), p = __gcd(n + y - x, n);
		if (p == n) continue;
		return p;
	}
	return 0;
}
vector<ull> factor(ull n) {
    if (n==1) return {};
    ull x = Pollard(n);
    if (x == n)
        return {x};
    auto l = factor(x), r = factor(n / x);
    l.insert(l.end(), all(r));
    return l;
}