結果
| 問題 |
No.312 置換処理
|
| コンテスト | |
| ユーザー |
 kuhaku
|
| 提出日時 | 2025-05-25 02:32:03 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 2,000 ms |
| コード長 | 18,216 bytes |
| コンパイル時間 | 3,956 ms |
| コンパイル使用メモリ | 308,412 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-25 02:32:09 |
| 合計ジャッジ時間 | 5,191 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 45 |
ソースコード
// competitive-verifier: PROBLEM
#include <algorithm>
#include <cstdint>
#include <iterator>
#include <numeric>
#include <vector>
#include <limits>
#include <utility>
namespace internal {
/// @param m `1 <= m`
/// @return x mod m
constexpr std::int64_t safe_mod(std::int64_t x, std::int64_t m) {
x %= m;
if (x < 0) x += m;
return x;
}
/// Fast modular multiplication by barrett reduction
/// Reference: https://en.wikipedia.org/wiki/Barrett_reduction
/// NOTE: reconsider after Ice Lake
struct barrett {
unsigned int _m;
std::uint64_t im;
// @param m `1 <= m`
explicit barrett(unsigned int m) : _m(m), im((std::uint64_t)(-1) / m + 1) {}
// @return m
unsigned int umod() const { return _m; }
// @param a `0 <= a < m`
// @param b `0 <= b < m`
// @return `a * b % m`
unsigned int mul(unsigned int a, unsigned int b) const {
std::uint64_t z = a;
z *= b;
std::uint64_t x = (std::uint64_t)(((__uint128_t)(z)*im) >> 64);
std::uint64_t y = x * _m;
return (unsigned int)(z - y + (z < y ? _m : 0));
}
};
/// @brief Montgomery modular multiplication
/// @see https://rsk0315.hatenablog.com/entry/2022/11/27/060616
struct montgomery {
/// @param m `1 <= m`
explicit constexpr montgomery(std::uint64_t m)
: _m(m), im(m), r((__uint128_t(1) << 64) % m), r2(-__uint128_t(m) % m) {
for (int i = 0; i < 5; ++i) im = im * (2 - _m * im);
im = -im;
}
/// @return m
constexpr std::uint64_t umod() const { return _m; }
/// @param a `0 <= a < m`
/// @param b `0 <= b < m`
/// @return `a * b % m`
constexpr std::uint64_t mul(std::uint64_t a, std::uint64_t b) const {
return mr((__uint128_t)a * mr((__uint128_t)b * r2));
}
constexpr std::uint64_t exp(std::uint64_t a, std::uint64_t b) const {
std::uint64_t res = 1, p = mr((__uint128_t)a * r2);
while (b) {
if (b & 1) res = mr((__uint128_t)res * p);
p = mr((__uint128_t)p * p);
b >>= 1;
}
return res;
}
constexpr bool same_pow(std::uint64_t x, int s, std::uint64_t n) const {
x = mr((__uint128_t)x * r2), n = mr((__uint128_t)n * r2);
for (int r = 0; r < s; r++) {
if (x == n) return true;
x = mr((__uint128_t)x * x);
}
return false;
}
private:
std::uint64_t _m, im, r, r2;
constexpr std::uint64_t mr(std::uint64_t x) const {
std::uint64_t res = (__uint128_t(x * im) * _m + x) >> 64;
return res >= _m ? res - _m : res;
}
constexpr std::uint64_t mr(__uint128_t x) const {
std::uint64_t res = (__uint128_t(std::uint64_t(x) * im) * _m + x) >> 64;
return res >= _m ? res - _m : res;
}
constexpr std::uint64_t mr(std::uint64_t a, std::uint64_t b) const {
__uint128_t t = (__uint128_t)a * b;
std::uint64_t x = t >> 64, y = t;
x = mr((__uint128_t)x * r), y = mr(y);
return x + y >= _m ? x + y - _m : x + y;
}
};
constexpr bool is_SPRP32(std::uint32_t n, std::uint32_t a) {
std::uint32_t d = n - 1, s = 0;
while ((d & 1) == 0) ++s, d >>= 1;
std::uint64_t cur = 1, pw = d;
while (pw) {
if (pw & 1) cur = (cur * a) % n;
a = (std::uint64_t)a * a % n;
pw >>= 1;
}
if (cur == 1) return true;
for (std::uint32_t r = 0; r < s; r++) {
if (cur == n - 1) return true;
cur = cur * cur % n;
}
return false;
}
/// given 2 <= n,a < 2^64, a prime, check whether n is a-SPRP
/// without 2,3,5,13,19,73,193,407521,299210837
constexpr bool is_SPRP64(const montgomery &m, std::uint64_t a) {
auto n = m.umod();
std::uint64_t d = n - 1;
int s = 0;
while ((d & 1) == 0) ++s, d >>= 1;
std::uint64_t cur = m.exp(a, d);
if (cur == 1) return true;
return m.same_pow(cur, s, n - 1);
}
constexpr bool is_prime_constexpr(std::uint32_t x) {
if (x == 2 || x == 3 || x == 5 || x == 7) return true;
if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) return false;
if (x < 121) return (x > 1);
std::uint64_t h = x;
h = ((h >> 16) ^ h) * 0x45d9f3b;
h = ((h >> 16) ^ h) * 0x45d9f3b;
h = ((h >> 16) ^ h) & 255;
constexpr uint16_t bases[] = {
15591, 2018, 166, 7429, 8064, 16045, 10503, 4399, 1949, 1295, 2776, 3620, 560, 3128, 5212, 2657,
2300, 2021, 4652, 1471, 9336, 4018, 2398, 20462, 10277, 8028, 2213, 6219, 620, 3763, 4852, 5012,
3185, 1333, 6227, 5298, 1074, 2391, 5113, 7061, 803, 1269, 3875, 422, 751, 580, 4729, 10239,
746, 2951, 556, 2206, 3778, 481, 1522, 3476, 481, 2487, 3266, 5633, 488, 3373, 6441, 3344,
17, 15105, 1490, 4154, 2036, 1882, 1813, 467, 3307, 14042, 6371, 658, 1005, 903, 737, 1887,
7447, 1888, 2848, 1784, 7559, 3400, 951, 13969, 4304, 177, 41, 19875, 3110, 13221, 8726, 571,
7043, 6943, 1199, 352, 6435, 165, 1169, 3315, 978, 233, 3003, 2562, 2994, 10587, 10030, 2377,
1902, 5354, 4447, 1555, 263, 27027, 2283, 305, 669, 1912, 601, 6186, 429, 1930, 14873, 1784,
1661, 524, 3577, 236, 2360, 6146, 2850, 55637, 1753, 4178, 8466, 222, 2579, 2743, 2031, 2226,
2276, 374, 2132, 813, 23788, 1610, 4422, 5159, 1725, 3597, 3366, 14336, 579, 165, 1375, 10018,
12616, 9816, 1371, 536, 1867, 10864, 857, 2206, 5788, 434, 8085, 17618, 727, 3639, 1595, 4944,
2129, 2029, 8195, 8344, 6232, 9183, 8126, 1870, 3296, 7455, 8947, 25017, 541, 19115, 368, 566,
5674, 411, 522, 1027, 8215, 2050, 6544, 10049, 614, 774, 2333, 3007, 35201, 4706, 1152, 1785,
1028, 1540, 3743, 493, 4474, 2521, 26845, 8354, 864, 18915, 5465, 2447, 42, 4511, 1660, 166,
1249, 6259, 2553, 304, 272, 7286, 73, 6554, 899, 2816, 5197, 13330, 7054, 2818, 3199, 811,
922, 350, 7514, 4452, 3449, 2663, 4708, 418, 1621, 1171, 3471, 88, 11345, 412, 1559, 194};
return is_SPRP32(x, bases[h]);
}
constexpr bool is_prime_constexpr(std::uint64_t x) {
if (x <= std::numeric_limits<std::uint32_t>::max()) return is_prime_constexpr((std::uint32_t)x);
if (x % 2 == 0 || x % 3 == 0 || x % 5 == 0 || x % 7 == 0) return false;
montgomery m(x);
constexpr std::uint64_t bases[] = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
for (auto a : bases) {
if (!is_SPRP64(m, a)) return false;
}
return true;
}
constexpr bool is_prime_constexpr(std::int64_t x) {
if (x < 0) return false;
return is_prime_constexpr(std::uint64_t(x));
}
/// @param n `0 <= n`
/// @param m `1 <= m`
/// @return `(x ** n) % m`
constexpr std::int64_t pow_mod_constexpr(std::int64_t x, std::int64_t n, int m) {
if (m == 1) return 0;
unsigned int _m = (unsigned int)(m);
std::uint64_t r = 1;
std::uint64_t y = safe_mod(x, m);
while (n) {
if (n & 1) r = (r * y) % _m;
y = (y * y) % _m;
n >>= 1;
}
return r;
}
/// Reference:
/// M. Forisek and J. Jancina,
/// Fast Primality Testing for Integers That Fit into a Machine Word
/// @param n `0 <= n`
constexpr bool is_prime_constexpr(int n) {
if (n <= 1) return false;
if (n == 2 || n == 7 || n == 61) return true;
if (n % 2 == 0) return false;
std::int64_t d = n - 1;
while (d % 2 == 0) d /= 2;
constexpr std::int64_t bases[3] = {2, 7, 61};
for (std::int64_t a : bases) {
std::int64_t t = d;
std::int64_t y = pow_mod_constexpr(a, t, n);
while (t != n - 1 && y != 1 && y != n - 1) {
y = y * y % n;
t <<= 1;
}
if (y != n - 1 && t % 2 == 0) { return false; }
}
return true;
}
template <int n>
constexpr bool is_prime = is_prime_constexpr(n);
/// @param b `1 <= b`
/// @return pair(g, x) s.t. g = gcd(a, b), xa = g (mod b), 0 <= x < b/g
constexpr std::pair<std::int64_t, std::int64_t> inv_gcd(std::int64_t a, std::int64_t b) {
a = safe_mod(a, b);
if (a == 0) return {b, 0};
std::int64_t s = b, t = a;
std::int64_t m0 = 0, m1 = 1;
while (t) {
std::int64_t u = s / t;
s -= t * u;
m0 -= m1 * u;
auto tmp = s;
s = t;
t = tmp;
tmp = m0;
m0 = m1;
m1 = tmp;
}
if (m0 < 0) m0 += b / s;
return {s, m0};
}
/// Compile time primitive root
/// @param m must be prime
/// @return primitive root (and minimum in now)
constexpr int primitive_root_constexpr(int m) {
if (m == 2) return 1;
if (m == 167772161) return 3;
if (m == 469762049) return 3;
if (m == 754974721) return 11;
if (m == 998244353) return 3;
int divs[20] = {};
divs[0] = 2;
int cnt = 1;
int x = (m - 1) / 2;
while (x % 2 == 0) x /= 2;
for (int i = 3; (std::int64_t)(i)*i <= x; i += 2) {
if (x % i == 0) {
divs[cnt++] = i;
while (x % i == 0) { x /= i; }
}
}
if (x > 1) { divs[cnt++] = x; }
for (int g = 2;; g++) {
bool ok = true;
for (int i = 0; i < cnt; i++) {
if (pow_mod_constexpr(g, (m - 1) / divs[i], m) == 1) {
ok = false;
break;
}
}
if (ok) return g;
}
}
template <int m>
constexpr int primitive_root = primitive_root_constexpr(m);
} // namespace internal
#include <array>
#include <bit>
/**
* @brief 疑似乱数生成器 SplitMix64
* @details 周期：$2^64-1$
*/
struct split_mix_64 {
using state_type = std::uint64_t;
using result_type = std::uint64_t;
constexpr split_mix_64() noexcept : state(1234567890) {}
constexpr split_mix_64(std::uint64_t seed) noexcept : state(seed) {}
static constexpr result_type min() noexcept { return std::numeric_limits<result_type>::min(); }
static constexpr result_type max() noexcept { return std::numeric_limits<result_type>::max(); }
constexpr result_type operator()() {
std::uint64_t z = (state += 0x9e3779b97f4a7c15);
z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
return z ^ (z >> 31);
}
constexpr state_type serialize() const noexcept { return state; }
constexpr void deserialize(const state_type &data) noexcept { state = data; }
constexpr void deserialize(state_type &&data) noexcept { state = std::move(data); }
template <std::size_t N>
constexpr std::array<std::uint64_t, N> generate_seed_sequence() noexcept {
std::array<std::uint64_t, N> seeds = {};
for (auto &seed : seeds) seed = operator()();
return seeds;
}
/// @brief a以上b以下の整数を生成
/// @return uint64_t [a, b]
std::uint64_t rand_range(std::uint64_t a, std::uint64_t b) {
if (a == split_mix_64::min() && b == split_mix_64::max()) return operator()();
return a + operator()() % (b - a + 1);
}
/// @brief 0.0以上1.0未満の浮動小数点数を生成
/// @return double [0, 1)
double random() { return (double)operator()() / max(); }
private:
state_type state;
};
/// @brief 疑似乱数生成器 xoroshiro128++
struct xoroshiro128 {
using state_type = std::array<std::uint64_t, 2>;
using result_type = std::uint64_t;
constexpr xoroshiro128() noexcept : state(split_mix_64{}.generate_seed_sequence<2>()) {}
constexpr xoroshiro128(std::uint64_t seed) noexcept : state(split_mix_64{seed}.generate_seed_sequence<2>()) {}
static constexpr result_type min() noexcept { return std::numeric_limits<result_type>::min(); }
static constexpr result_type max() noexcept { return std::numeric_limits<result_type>::max(); }
constexpr result_type operator()() {
const std::uint64_t s0 = state[0];
std::uint64_t s1 = state[1];
const std::uint64_t result = std::rotl(s0 + s1, 17) + s0;
s1 ^= s0;
state[0] = std::rotl(s0, 49) ^ s1 ^ (s1 << 21), state[1] = std::rotl(s1, 28);
return result;
}
bool operator==(const xoroshiro128 &rhs) noexcept { return (state == rhs.state); }
bool operator!=(const xoroshiro128 &rhs) noexcept { return (state != rhs.state); }
constexpr state_type serialize() const noexcept { return state; }
constexpr void deserialize(const state_type &data) noexcept { state = data; }
constexpr void deserialize(state_type &&data) noexcept { state = std::move(data); }
/// @brief a以上b以下の整数を生成
/// @return uint64_t [a, b]
std::uint64_t rand_range(std::uint64_t a, std::uint64_t b) {
if (a == xoroshiro128::min() && b == xoroshiro128::max()) return operator()();
return a + operator()() % (b - a + 1);
}
/// @brief 0.0以上1.0未満の浮動小数点数を生成
/// @return double [0, 1)
double random() noexcept { return (double)operator()() / max(); }
private:
state_type state;
};
namespace internal {
std::uint64_t pollard_rho(std::uint64_t n) {
static xoroshiro128 rnd;
if (~n & 1) return 2;
if (internal::is_prime_constexpr(n)) return n;
std::uint64_t r = 0, g = 1;
auto f = [&](std::uint64_t x) -> std::uint64_t { return ((__uint128_t)x * x + r) % n; };
std::uniform_int_distribution<std::uint64_t> gen(2, n - 1);
while (true) {
std::uint64_t x, y, z, ys, q = 1;
r = gen(rnd), y = gen(rnd);
g = 1;
constexpr int m = 128;
for (int r = 1; g == 1; r <<= 1) {
x = y;
for (int i = 0; i < r; ++i) y = f(y);
for (int k = 0; g == 1 && k < r; k += m) {
ys = y;
for (int i = 0; i < m && i < r - k; ++i) q = (__uint128_t)q * (x + n - (y = f(y))) % n;
g = std::gcd(q, n);
}
}
if (g == n) {
do {
z = x + n - (ys = f(ys));
if (z >= n) z -= n;
g = std::gcd(z, n);
} while (g == 1);
}
if (g != n) break;
}
return g;
}
std::vector<std::uint64_t> inner_factorize(std::uint64_t n) {
if (n <= 1) return {};
std::uint64_t p = pollard_rho(n);
if (p == n) return {p};
auto l = inner_factorize(p);
auto r = inner_factorize(n / p);
std::copy(r.begin(), r.end(), std::back_inserter(l));
return l;
}
} // namespace internal
/// @brief 素因数分解
std::vector<std::uint64_t> factorize(std::uint64_t n) {
auto res = internal::inner_factorize(n);
std::sort(res.begin(), res.end());
return res;
}
std::uint64_t number_of_divisors(std::vector<std::uint64_t> v) {
std::sort(v.begin(), v.end());
int c = 0;
std::uint64_t res = 1;
for (int i = 0; i < (int)v.size(); ++i) {
if (i == 0 || v[i] == v[i - 1]) {
++c;
} else {
res *= c + 1;
c = 1;
}
}
return res * (c + 1);
}
std::uint64_t number_of_divisors(std::uint64_t n) { return number_of_divisors(internal::inner_factorize(n)); }
#ifdef ATCODER
#pragma GCC target("sse4.2,avx512f,avx512dq,avx512ifma,avx512cd,avx512bw,avx512vl,bmi2")
#endif
#pragma GCC optimize("Ofast,fast-math,unroll-all-loops")
#include <bits/stdc++.h>
#ifndef ATCODER
#pragma GCC target("sse4.2,avx2,bmi2")
#endif
template <class T, class U>
constexpr bool chmax(T &a, const U &b) {
return a < (T)b ? a = (T)b, true : false;
}
template <class T, class U>
constexpr bool chmin(T &a, const U &b) {
return (T)b < a ? a = (T)b, true : false;
}
constexpr std::int64_t INF = 1000000000000000003;
constexpr int Inf = 1000000003;
constexpr double EPS = 1e-7;
constexpr double PI = 3.14159265358979323846;
#define FOR(i, m, n) for (int i = (m); i < int(n); ++i)
#define FORR(i, m, n) for (int i = (m)-1; i >= int(n); --i)
#define FORL(i, m, n) for (int64_t i = (m); i < int64_t(n); ++i)
#define rep(i, n) FOR (i, 0, n)
#define repn(i, n) FOR (i, 1, n + 1)
#define repr(i, n) FORR (i, n, 0)
#define repnr(i, n) FORR (i, n + 1, 1)
#define all(s) (s).begin(), (s).end()
struct Sonic {
Sonic() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout << std::fixed << std::setprecision(20);
}
constexpr void operator()() const {}
} sonic;
using namespace std;
using ll = std::int64_t;
using ld = long double;
template <class T, class U>
std::istream &operator>>(std::istream &is, std::pair<T, U> &p) {
return is >> p.first >> p.second;
}
template <class T>
std::istream &operator>>(std::istream &is, std::vector<T> &v) {
for (T &i : v) is >> i;
return is;
}
template <class T, class U>
std::ostream &operator<<(std::ostream &os, const std::pair<T, U> &p) {
return os << '(' << p.first << ',' << p.second << ')';
}
template <class T>
std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
for (auto it = v.begin(); it != v.end(); ++it) os << (it == v.begin() ? "" : " ") << *it;
return os;
}
template <class Head, class... Tail>
void co(Head &&head, Tail &&...tail) {
if constexpr (sizeof...(tail) == 0) std::cout << head << '\n';
else std::cout << head << ' ', co(std::forward<Tail>(tail)...);
}
template <class Head, class... Tail>
void ce(Head &&head, Tail &&...tail) {
if constexpr (sizeof...(tail) == 0) std::cerr << head << '\n';
else std::cerr << head << ' ', ce(std::forward<Tail>(tail)...);
}
void Yes(bool is_correct = true) { std::cout << (is_correct ? "Yes\n" : "No\n"); }
void No(bool is_not_correct = true) { Yes(!is_not_correct); }
void YES(bool is_correct = true) { std::cout << (is_correct ? "YES\n" : "NO\n"); }
void NO(bool is_not_correct = true) { YES(!is_not_correct); }
void Takahashi(bool is_correct = true) { std::cout << (is_correct ? "Takahashi" : "Aoki") << '\n'; }
void Aoki(bool is_not_correct = true) { Takahashi(!is_not_correct); }
int main(void) {
ll n;
cin >> n;
if (n % 3 == 0) {
co(3);
return 0;
}
if (n % 4 == 0) {
co(4);
return 0;
}
while (n % 2 == 0) n /= 2;
auto v = factorize(n);
for (auto p : v) {
if (p >= 3) {
co(p);
return 0;
}
}
co(n);
return 0;
}