算法笔记

Appearance

质因分解 ​

暴力 ​

cpp
auto factor(i64 n) {
	std::vector<i64> ret;
	for (int i = 2; i64(i) * i <= n; i++) {
		for (; n % i == 0; n /= i)
			ret.push_back(i);
	}
	if (n > 1)
		ret.push_back(n);
	return ret;
}

筛优化 ​

cpp
auto factor(i64 n) {
	std::vector<i64> ans;
	for (int i : primes) {
		if (1ll * i * i > n)
			break;
		for (; n % i == 0; n /= i)
			ans.push_back(i);
	}
	if (n > 1)
		ans.push_back(n);
	return ans;
}

LPF 优化 ​

cpp
auto factor(i64 n) {
	std::vector<i64> ret;
	for (; n > 1; n /= lpf[n])
		ret.push_back(lpf[n]);
	return ret;
}

Pollard Rho ​

cpp
i64 pollard_rho(i64 N) {
	if (N % 2 == 0)
		return 2;
	if (miller_rabin(N))
		return N;
	while (true) {
		auto f = [N, c = rand() % (N - 1) + 1](i64 x) {
			return (i128(x) * x + c) % N;
		};
		i64 x = 0, y = 0, p = 1, q = 1;
		do {
			int w = 128;
			do {
				p = q, x = f(x), y = f(f(y));
				q = i128(p) * std::abs(x - y) % N;
			} while (w-- && q != 0);
			i64 d = std::gcd(p, N);
			if (d > 1 && d != N)
				return d;
		} while (x != y);
	}
}

auto factor(i64 x) {
	std::vector<i64> v;
	if (x == 1)
		return v;
	auto dfs = [&](auto &&self, i64 u) -> void {
		i64 fac = pollard_rho(u);
		if (fac == u)
			v.push_back(u);
		else
			self(self, fac), self(self, u / fac);
	};
	dfs(dfs, x);
	std::sort(v.begin(), v.end());
	return v;
}
cpp
using i128 = __int128_t;

i64 qpow64(i64 a, i64 n, i64 m) {
 i64 ret = 1 % m;
 for (; n; n /= 2) {
  if (n & 1)
   ret = i128(a) * ret % m;
  a = i128(a) * a % m;
 }
 return ret;
}

bool is_prime_small(i64 n) {
 if (n < 64)
  return (0x28208a20a08a28ac >> n) & 1;
 if ((0xdf75d77d >> (n % 30)) & 1)
  return false;
 if (n % 7 == 0 || n % 11 == 0)
  return false;
 return true;
}

bool miller_rabin(i64 n) {
 if (!is_prime_small(n))
  return false;
 i64 a = n - 1;
 a /= a & -a;
 for (int p : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
  if (n <= p)
   return true;
  i64 t = a, v = qpow64(p, t, n);
  while (t != n - 1 && v != 1 && v != n - 1)
   v = i128(v) * v % n, t *= 2;
  if (v != n - 1 && t % 2 == 0)
   return false;
 }
 return true;
}

i64 pollard_rho(i64 N) {
 if (N % 2 == 0)
  return 2;
 if (miller_rabin(N))
  return N;
 while (true) {
  auto f = [N, c = rand() % (N - 1) + 1](i64 x) {
   return (i128(x) * x + c) % N;
  };
  i64 x = 0, y = 0, p = 1, q = 1;
  do {
   int w = 128;
   do {
    p = q, x = f(x), y = f(f(y));
    q = i128(p) * std::abs(x - y) % N;
   } while (w-- && q != 0);
   i64 d = std::gcd(p, N);
   if (d > 1 && d != N)
    return d;
  } while (x != y);
 }
}
auto factor(i64 x) {
 std::vector<i64> v;
 if (x == 1)
  return v;
 auto dfs = [&](auto &&self, i64 u) -> void {
  i64 fac = pollard_rho(u);
  if (fac == u)
   v.push_back(u);
  else
   self(self, fac), self(self, u / fac);
 };
 dfs(dfs, x);
 std::sort(v.begin(), v.end());
 return v;
}