백준 7501번 C++ 풀이

문제

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

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

---

풀이

 일단 영어 지문을 읽으면 토악질이 나오는 나지만, 그래도 해석은 가능한 수준의 영어라 읽어보았다. 이러니 저러니하지만, 정리하면 구간 [A, B]에서 다음을 만족하는 정수를 K를 구하는 문제이다.

• K는 홀수이다.
• (K-1)! ł K^2. 즉 (K-1)!은 K^2로 나누어 떨어지지 않는다.

정수론에서 제일 특별한 수는 항상 소수이다. 이 문제에서도 소수와 소수가 아닌 경우를 생각해보자. 

 

 K가 소수라면, (K-1)!은 절대로 K^2로 나누어 떨어지지 않는다. 증명도 간단하다. 귀류법으로 생각해서 (K-1)!이 K^2으로 나누어 떨어진다고 해보자. 이는 (K-1)!의 소인수에 K가 들어가있다는 뜻이 된다. 하지만, (K-1)!의 소인수에는 K가 들어갈 수 없다. K보다 작은 수들의 곱으로 나타나기 때문이다. 또한, K는 소수이기 때문에 다른 수들의 곱으로 나타낼 수 없다. 그렇기 때문에 K가 소수라면 (K-1)!은 K^2로 절대 나누어떨어지지 않는다.

 

 K가 소수가 아니라면, (K-1)! ł K^2인지 확인해야한다. 하지만 K의 최댓값이 10^18인데 (10^18-1)!을 어떻게 구하겠는가. 꼼수를 하나 써보자. K^2가 (K-1)!을 나누어 떨어지게 하려면, K^2가 (K-1)!의 인수여야 한다. 이말은, K^2의 인수들이 모두 (K-1)!의 인수라는 뜻이다. K를 a_0^p_0 * a_1^p_1 * ... * a_x^p_x라고 하면, K^2는 a_0^2p_0 * a_1^2p_1 * ... * a_x^2p_x 이다. K를 폴라드-로를 사용해 빠르게 인수분해한 후, 소인수들의 개수를 2배씩 한다. 이제, (K-1)!에서 K^2의 모든 소인수들이 K^2에 있는것보다 같거나 더 많으면 그것은 (K-1)! | K^2라는 뜻이 되기에 조건을 만족하지 못한다. 이를 코드로 옮기면 된다. 

코드

#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(int seed = (unsigned)chrono::steady_clock::now().time_since_epoch().count()) : 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;
	}
} M;

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(ret.begin(), ret.end());
		return ret;
	}
} P;

ll a, b;

void sol() {
	unordered_map<ll, ll> fac;
	ll tmp;

	if (a % 2 == 0) a++;

	for(ll k = a; k <= b; k += 2) {
		if (M.IsPrime(k)) {
			cout << k << ' ';
		}
		else {
			fac.clear();
			for(ll f : P.Factorize(k)) {
				if (fac.find(f) != fac.end()) {
					fac[f] += 2LL;
				}
				else {
					fac.emplace(f, 2LL);
				}
			}

			bool check = true;

			for(auto& [f, cnt] : fac) {
				if (!check) break;

				ll tmp = k - 1LL;
				ll e = 0LL;
				while (tmp >= f) {
					e += tmp / f;
					tmp /= f;
				}
				check = e >= cnt;
			}

			if (!check) cout << k << ' ';
		}
	}
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	cin >> a >> b;
	sol();
}