백준 10854번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초	256vMB	플래티넘 1

---

풀이

 밀린 문제 정리하기. 폴라드-로 남은 문제이다.

 

 말은 번지르르한데, 결국 n의 인수의 개수를 세는 문제이다. n이 크기 때문에 폴라드로 인수분해를 통해 찾아주고, 약수의 개수를 세면 된다.

코드

#include<bits/stdc++.h>
using namespace std;
using ll = int64_t;
using ull = 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);
	}
} Rand;

struct MillerRabin {
	ll Mul(ll x, ll y, ll MOD) {
		ll ret = x * y - MOD * ull(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(ret.begin(), ret.end());
		return ret;
	}
} P;


int main() {
	cin.tie(0)->sync_with_stdio(0);
	ll n, ans=1; cin >> n;
	map<ll, int> fac;
    for (auto& i : P.Factorize(n)) fac[i]++;
	for (auto& [_, k] : fac) ans *= k + 1;
	cout << ans;
}