素因数分解をO(N^(1/4))で行う (daylight/math/rho.hpp)

• View this file on GitHub
• Last update: 2024-12-26 20:32:55+09:00
• Include: #include "daylight/math/rho.hpp"

Depends on

• 基本テンプレート (daylight/base.hpp)
• 繰り返し2乗法でa^p mod mを求める (daylight/math/powmod.hpp)
• 素数判定 (O(log(N))) (daylight/math/primality_test.hpp)

Verified with

• test/aoj/ntl/1_A.test.2.cpp
• test/yosupo/number_theory/factorize.test.cpp

Code

#include "daylight/base.hpp"
#include "daylight/math/powmod.hpp"
#include "daylight/math/primality_test.hpp"

ll find_prime_factor(ll N) {
	using i128 = __int128_t;
	if(N % 2 == 0) {
		return 2;
	}
	int b = int(sqrt(sqrt(sqrt(N)))) + 1;
	FOR(c, 1, N) {
		auto f = [&](ll a) -> ll {
			return pow_mod(a, 2, N) + c;
		};
		ll y = 6;
		ll g = 1;
		i128 q = 1;
		int r = 1;
		int k = 0;
		ll ys = 0;
		ll x = 0;
		while(g == 1) {
			x = y;
			while(k < 3 * r / 4) {
				y = f(y);
				k++;
			}
			while(k < r && g == 1) {
				ys = y;
				REP(i, min(b, r - k)) {
					y = f(y);
					q *= abs(x - y);
					q %= N;
				}
				g = gcd(ll(q), N);
				k += b;
			}
			k = r;
			r *= 2;
		}
		if(g == N) {
			g = 1;
			y = ys;
			while(g == 1) {
				y = f(y);
				g = gcd(abs(x - y), N);
			}
		}
		if(g == N) {
			continue;
		}
		if(is_prime(g)) {
			return g;
		}
		if(is_prime(N / g)) {
			return N / g;
		}
		return find_prime_factor(g);
	}
	assert(false);
}

/// @brief 素因数分解をO(N^(1/4))で行う
/// @param N 素因数分解する整数
/// @return map: p^eが含まれる場合map[p] = e
map<ll, int> factorize(ll N) {
	map<ll, int> ret;
	while(!is_prime(N) && N > 1) {
		ll p = find_prime_factor(N);
		int s = 0;
		while(N % p == 0) {
			N /= p;
			s++;
		}
		ret[p] = s;
	}
	if(N > 1) {
		ret[N] = 1;
	}
	return ret;
}

Traceback (most recent call last):
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj_resolve/resolver.py", line 181, in resolve
    bundled_code = language.bundle(path, basedir=basedir)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus.py", line 252, in bundle
    bundler.update(path)
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 482, in update
    self.update(
  File "/home/runner/.local/lib/python3.10/site-packages/competitive_verifier/oj/verify/languages/cplusplus_bundle.py", line 477, in update
    raise BundleErrorAt(
competitive_verifier.oj.verify.languages.cplusplus_bundle.BundleErrorAt: daylight/base.hpp: line 103: unable to process #include in #if / #ifdef / #ifndef other than include guards

Back to top page