#1195586 (C++23) No.2798 Multiple Chain

• 問題: No.2798 Multiple Chain
• ユーザー: kwm_t
• 提出日時: 2026-10-27 20:39:40
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0 + ACL)
• 結果: AC
• 実行時間: 4 ms / 2,000 ms
• コード長: 5,810 bytes
• コンパイル時間: 3,052 ms
• コンパイル使用メモリ: 348,192 KB
• 実行使用メモリ: 9,920 KB
• 最終ジャッジ日時: 2026-10-27 20:39:47
• 合計ジャッジ時間: 6,882 ms
• ジャッジサーバーID （参考情報）: judge5_0 / judge3_0

ファイルパターン	結果
sample	AC * 3
other	AC * 52

ソースコード

#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
// using namespace atcoder;
// using mint = modint1000000007;
// const int mod = 1000000007;
// using mint = modint998244353;
// const int mod = 998244353;
// const int INF = 1e9;
// const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i, l, r) for (int i = (l); i < (r); ++i)
#define rrep(i, n) for (int i = (n)-1; i >= 0; --i)
#define rrep2(i, l, r) for (int i = (r)-1; i >= (l); --i)
#define all(x) (x).begin(), (x).end()
#define allR(x) (x).rbegin(), (x).rend()
#define P pair<int, int>
template<typename A, typename B> inline bool chmax(A& a, const B& b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A& a, const B& b) { if (a > b) { a = b; return true; } return false; }
/**
 * @file integer.hpp
 * @brief 整数型に関する補助機能
 * @author kwm_t
 * @see https://github.com/kwm-t/cp-library/blob/main/base/integer.hpp
 */
#ifndef KWM_T_BASE_INTEGR_HPP
#define KWM_T_BASE_INTEGR_HPP

#include <vector>

 /**
  * @brief ローカル環境用(MSC)int128
  */
#ifdef _MSC_VER
using int128 = long long;
#else
using int128 = __int128;
std::ostream& operator<<(std::ostream& dest, int128 value) {
	if (value == 0) {
		return dest << 0;
	}
	if (value < 0) {
		dest << '-';
		value = -value;
	}
	char buffer[128];
	char* p = end(buffer);
	while (value > 0) {
		*--p = '0' + (value % 10);
		value /= 10;
	}
	return dest.write(p, end(buffer) - p);
}
#endif

#endif // KWM_T_BASE_INTEGR_HPP

/**
 * @file miller_rabin.hpp
 * @brief Miller-Rabin 素数判定法
 * @author kwm_t
 * @see https://github.com/kwm-t/cp-library/blob/main/math/miller_rabin.hpp
 */
#ifndef KWM_T_MATH_MILLER_RABIN_HPP
#define KWM_T_MATH_MILLER_RABIN_HPP

#include <vector>
 // #include "base/integer.hpp"

namespace kwm_t::math {

/**
 * @brief Miller-Rabin 素数判定（64bit対応・確定的）
 *
 * 計算量:
 *   O(log n)
 *
 * 制約:
 *   - n < 2^64
 *
 * verified:
 *   https://judge.yosupo.jp/submission/367299
 */
struct MillerRabin {
private:
	static int128 modmul(int128 a, int128 b, int128 mod) {
		return (a * b) % mod;
	}

	static long long modpow(long long a, long long e, long long mod) {
		int128 res = 1;
		int128 base = a % mod;

		while (e) {
			if (e & 1) res = modmul(res, base, mod);
			base = modmul(base, base, mod);
			e >>= 1;
		}
		return (long long)res;
	}

public:
	static bool is_prime(long long n) {
		if (n < 2) return false;

		// 小さい素数で弾く
		for (long long p : {2, 3, 5, 7, 11, 13, 17, 19, 23}) {
			if (n == p) return true;
			if (n % p == 0 && n != p) return false;
		}

		long long d = n - 1;
		int s = 0;
		while ((d & 1) == 0) {
			d >>= 1;
			++s;
		}

		// 64bitで確定的な基底
		static const long long bases[] = {
			2, 325, 9375, 28178, 450775, 9780504, 1795265022
		};

		for (long long a : bases) {
			if (a % n == 0) continue;

			long long x = modpow(a, d, n);
			if (x == 1 || x == n - 1) continue;

			bool composite = true;
			for (int r = 1; r < s; ++r) {
				x = modmul(x, x, n);
				if (x == n - 1) {
					composite = false;
					break;
				}
			}

			if (composite) return false;
		}

		return true;
	}
};

} // namespace kwm_t::math

#endif // KWM_T_MATH_MILLER_RABIN_HPP

/**
 * @file pollard_rho.hpp
 * @brief Pollard's rho 法
 * @author kwm_t
 * @see https://github.com/kwm-t/cp-library/blob/main/math/pollard_rho.hpp
 */
#ifndef KWM_T_MATH_POLLARD_RHO_HPP
#define KWM_T_MATH_POLLARD_RHO_HPP

#include <vector>
#include <random>
#include <numeric>
#include <cstdint>
 // #include "base/integer.hpp"
 // #include "miller_rabin.hpp"

namespace kwm_t::math {

/**
 * @brief Pollard Rho による素因数分解（64bit対応）
 *
 * 計算量:
 *   平均 O(n^{1/4})
 *
 * 制約:
 *   - n < 2^64
 *
 * verified:
 *   https://judge.yosupo.jp/submission/367301
 */
struct PollardRho {
private:
	std::mt19937_64 rng;

	static int128 modmul(int128 a, int128 b, int128 mod) {
		return (a * b) % mod;
	}

	static long long f(long long x, long long c, long long mod) {
		return (modmul(x, x, mod) + c) % mod;
	}

	long long pollard(long long n) {
		if (n % 2 == 0) return 2;

		std::uniform_int_distribution<long long> dist(2, n - 2);

		while (true) {
			long long x = dist(rng);
			long long y = x;
			long long c = dist(rng);
			long long d = 1;

			while (d == 1) {
				x = f(x, c, n);
				y = f(f(y, c, n), c, n);

				long long diff = x > y ? x - y : y - x;
				d = std::gcd(diff, n);
			}

			if (d != n) return d;
		}
	}

	void factor_rec(long long n, std::vector<long long>& res) {
		if (n == 1) return;
		if (MillerRabin::is_prime(n)) {
			res.push_back(n);
			return;
		}

		long long d = pollard(n);
		factor_rec(d, res);
		factor_rec(n / d, res);
	}

public:
	PollardRho() : rng(std::random_device{}()) {}

	/**
	 * @brief 素因数分解(非ソート)
	 */
	std::vector<long long> factor(long long n) {
		std::vector<long long> res;
		factor_rec(n, res);
		return res;
	}
};

} // namespace kwm_t::math

#endif // KWM_T_MATH_POLLARD_RHO_HPP


int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	//Rho rho;
	long long n; cin >> n;
	kwm_t::math::PollardRho pr;
	auto v = pr.factor(n);
	map<long long, int>mp;
	rep(i, v.size()) mp[v[i]]++;
	long long ans = 1;
	vector<long long> devide = {
	1, 1, 2, 3, 5,
	7, 11, 15, 22, 30,
	42, 56, 77, 101, 135,
	176, 231, 297, 385, 490,
	627, 792, 1002, 1255, 1575,
	1958, 2436, 3010, 3718, 4565,
	5604, 6842, 8349, 10143, 12310,
	14883, 17977, 21637, 26015, 31185,
	37338, 44583, 53174, 63261, 75175,
	89134, 105558, 124754, 147273, 173525,
	204226, 239943, 281589, 329931, 386155,
	451276, 526823, 614154, 715220, 831820
	};
	for (auto [k, v] : mp) ans *= devide[v];
	cout << ans << endl;
	return 0;
	return 0;
}