백준 13926번 C++ 풀이

문제

https://www.acmicpc.net/problem/13926

시간 제한	메모리 제한	solved.ac 티어
2초	512MB	다이아몬드 5

---

풀이

 밀린 문제 정리하기. 오일러 피함수 문제이다. 그런데 밀러라빈 소수 판별법과 폴라드-로 알고리즘을 섞은... 괴랄한 알고리즘의 문제이다. 저번 GCD(n,k) = 1와 설명은 같은 문제이다. (https://codejin.tistory.com/306)

백준 11689번 C++ 풀이

 저번 문제의 경우 n이 최대 n = 10^12이고, 내가 구현한 오일러 피함수의 경우, 시간복잡도가 O(n^1/2)이기 때문에 n이 10^12로 들어오더라도 탐색 횟수는 10^6번, 그러니까 100만번의 탐색이면 끝난다. 1초안에 충분히 풀 수 있는 상황이었다.

 

 하지만 이번 경우는 말이 다르다. n이 최대 10^18까지 들어오며, 11689번의 코드를 그대로 사용한다면 10^9번의 탐색, 그러니까 10억번의 탐색을 진행해야한다. 음 딱봐도 이건 안될거 같다는 느낌이 온다. 괜히 다이아일리가 없다. 11689번에서 설명했듯이, 내 코드는 에라토스테네스의 체의 구현 방식을 차용했기 때문에 가능했다. 오일러 피함수가 빠르게 동작하려면 n의 소인수를 모두 알고 있는 상태에서 바로 계산하는 것이다. 하지만 에라토스테네스의 체는 그렇게 큰 수까지 찾는건 어렵다. 만약 해당 문제에서 에라토스테네스의 체를 사용하고자 한다면, 비트마스킹과 같이 더 적은 메모리공간을 차지하는 선에서 해야하겠지만, 테스트해본 10억비트를 사용하려고 하면 segmentation fault가 발생한다. 아예 에라토스테네스의 체를 사용할 수가 없는 것이다. 다른 소인수분해 알고리즘을 찾아볼 필요가 있다.

 

 에라토스테네스의 체의 시간복잡도는 O(n^1/2)이기 때문에 불가능했다. 더 빠른 알고리즘을 사용할 필요가 있다. 다행히도, O(n^1/4)의 시간복잡도를 가지는 인수분해 알고리즘이 존재한다. 바로 폴라드-로 알고리즘이다. 폴라드-로 알고리즘은 다시 밀러-라빈 소수판별법과 같이 사용된다. ...솔직히 부끄러운 이야기지만 폴라드-로를 제대로 이해했다고 하진 못하겠다. 밀러-라빈 소수 판별법은 이해하는데 성공했지만, 폴라드-로의 난이도는 상상을 초월했다. 유명한 백준 랭커인 jinhan님의 설명을 참조하는게 좋을 것 같다. 그런데 이 글을 찾아서 들어오는 백준 유저라면 애초에 이정도 실력은 가지고 있을테니 이미 이해하고 있지 않을까 싶기도 한다. 전 허접이라서요...

https://blog.naver.com/jinhan814/222141831551

폴라드-로(Pollard-rho) 소인수 분해 알고리즘

 

폴라드-로 알고리즘의 의의는 큰 수에 대해서도 빠른 인수분해가 가능하다는 것이다. 이를 통해 소인수를 모두 찾아냈다면, 나머지는 오일러 피함수에 소인수들을 대입하며 답을 구하면 끝인 문제이다.

코드

// 밀러라빈과 폴라드로는 jinhan님이 구현한
// https://www.acmicpc.net/source/share/f3d355ae97e44d679954b5f98c03dd1c
// 을 이용했다. 밀러라빈과 폴라드로 구현은 굳이 안봐도 되겠지만, 일단 풀코드를 첨부한다.

#include <bits/stdc++.h>
#define ALL(X) X.begin(), X.end()
using namespace std;
using ll = int64_t;
using ul = uint64_t;

struct Random {
	mt19937 rd;
	Random() : rd((unsigned)chrono::steady_clock::now().time_since_epoch().count()) {}
	Random(int seed) : rd(seed) {}
	template<typename T = int>
	T GetInt(T l = 0, T r = 32767) {
		return uniform_int_distribution<T>(l, r)(rd);
	}
	double GetDouble(double l = 0, double r = 1) {
		return uniform_real_distribution<double>(l, r)(rd);
	}
} Rand;

struct MillerRabin {
	ll Mul(ll x, ll y, ll MOD) {
		ll ret = x * y - MOD * ul(1.L / MOD * x * y);
		return ret + MOD * (ret < 0) - MOD * (ret >= (ll)MOD);
	}
	ll _pow(ll x, ll n, ll MOD) {
		ll ret = 1; x %= MOD;
		for (; n; n >>= 1) {
			if (n & 1) ret = Mul(ret, x, MOD);
			x = Mul(x, x, MOD);
		}
		return ret;
	}
	bool Check(ll x, ll p) {
		if (x % p == 0) return 0;
		for (ll d = x - 1; ; d >>= 1) {
			ll t = _pow(p, d, x);
			if (d & 1) return t != 1 && t != x - 1;
			if (t == x - 1) return 0;
		}
	}
	bool IsPrime(ll x) {
		if (x == 2 || x == 3 || x == 5 || x == 7) return 1;
		if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) return 0;
		if (x < 121) return x > 1;
		if (x < 1ULL << 32) for (auto& i : { 2, 7, 61 }) {
			if (x == i) return 1;
			if (x > i && Check(x, i)) return 0;
		}
		else for (auto& i : { 2, 325, 9375, 28178, 450775, 9780504, 1795265022 }) {
			if (x == i) return 1;
			if (x > i && Check(x, i)) return 0;
		}
		return 1;
	}
};

struct PollardRho : public MillerRabin {
	void Rec(ll n, vector<ll>& v) {
		if (n == 1) return;
		if (~n & 1) { v.push_back(2); Rec(n >> 1, v); return; }
		if (IsPrime(n)) { v.push_back(n); return; }
		ll a, b, c, g = n;
		auto f = [&](ll x) { return (c + Mul(x, x, n)) % n; };
		do {
			if (g == n) {
				a = b = Rand.GetInt<ll>(0, n - 3) + 2;
				c = Rand.GetInt<ll>(0, 19) + 1;
			}
			a = f(a); b = f(f(b)); g = gcd(abs(a - b), n);
		} while (g == 1);
		Rec(g, v); Rec(n / g, v);
	}
	vector<ll> Factorize(ll n) {
		vector<ll> ret; Rec(n, ret);
		sort(ALL(ret));
		return ret;
	}
} P;

ul euler_phi(ul n) {
	ul res = n;
	auto fac = P.Factorize(n);
	fac.erase(unique(ALL(fac)), fac.end());

	for(auto& x : fac) {
		res /= x;
		res *= (x - 1);
		while (n % x == 0) n /= x;
	}

	if (n != 1) {
		res /= n;
		res *= (n - 1);
	}

	return res;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	ul n; cin >> n;
	cout << euler_phi(n);
}