結果
| 問題 | No.3485 Find 495-like Number |
| コンテスト | |
| ユーザー |
 ロロ宮
|
| 提出日時 | 2026-04-06 08:17:55 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 3 ms / 5,000 ms |
| コード長 | 37,644 bytes |
| 記録 | |
| コンパイル時間 | 5,411 ms |
| コンパイル使用メモリ | 377,892 KB |
| 実行使用メモリ | 6,400 KB |
| 最終ジャッジ日時 | 2026-04-06 08:18:11 |
| 合計ジャッジ時間 | 9,820 ms |
|
ジャッジサーバーID （参考情報） |
judge3_0 / judge1_1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
// [TEMPLATE_BEGIN]
#include <bits/stdc++.h>
#include <iostream>
#include <tuple>
#include <type_traits>
#include <vector>
// ==================== 単一値・基本入力 ====================
/**
* @brief 標準入出力の高速化を行う。main関数の最初で呼ぶことを推奨。
*/
inline void fast_io() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(nullptr);
}
/**
* @brief 任意の数の変数を標準入力から読み込む
* @tparam Ts 引数の型パック
* @param args 読み込み先の変数
*/
template <typename... Ts>
inline void scan(Ts&... args) {
(std::cin >> ... >> args);
}
/**
* @brief 単一の値を標準入力から読み込む
* @tparam T 読み込む値の型 (デフォルト: int)
* @return 読み込んだ値
*/
template <typename T = int>
inline T read() {
T x;
std::cin >> x;
return x;
}
// ==================== ベクター入力 ====================
/**
* @brief 1次元ベクターを標準入力から読み込む（算術型用、offset 付き）
* @tparam T 要素の型 (デフォルト: int)
* @param n 要素数
* @param offset 読み込み時に引く値 (デフォルト: 0)
* @return 読み込んだベクター
*/
template <typename T = int>
requires std::is_arithmetic_v<T>
inline std::vector<T> read_vec(int n, T offset = 0) {
std::vector<T> v(n);
for (auto& x : v) {
std::cin >> x;
x -= offset;
}
return v;
}
/**
* @brief 1次元ベクターを標準入力から読み込む（非算術型用）
* @tparam T 要素の型
* @param n 要素数
* @return 読み込んだベクター
*/
template <typename T>
requires(!std::is_arithmetic_v<T>)
inline std::vector<T> read_vec(int n) {
std::vector<T> v(n);
for (auto& x : v) {
std::cin >> x;
}
return v;
}
/**
* @brief 2次元ベクターを標準入力から読み込む（算術型用、offset 付き）
* @tparam T 要素の型 (デフォルト: int)
* @param h 行数
* @param w 列数
* @param offset 読み込み時に引く値 (デフォルト: 0)
* @return 読み込んだ h×w の2次元ベクター
*/
template <typename T = int>
requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_vec2(int h, int w, T offset = 0) {
std::vector<std::vector<T>> v(h, std::vector<T>(w));
for (auto& row : v) {
for (auto& x : row) {
std::cin >> x;
x -= offset;
}
}
return v;
}
/**
* @brief 2次元ベクターを標準入力から読み込む（非算術型用）
* @tparam T 要素の型
* @param h 行数
* @param w 列数
* @return 読み込んだ h×w の2次元ベクター
*/
template <typename T>
requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_vec2(int h, int w) {
std::vector<std::vector<T>> v(h, std::vector<T>(w));
for (auto& row : v) {
for (auto& x : row) {
std::cin >> x;
}
}
return v;
}
/**
* @brief 各行の最初に要素数が与えられる可変長2次元ベクターを標準入力から読み込む（算術型用、offset 付き）
* @tparam T 要素の型 (デフォルト: int)
* @param h 行数
* @param offset 読み込み時に引く値 (デフォルト: 0)
* @return 読み込んだ可変長の2次元ベクター
*/
template <typename T = int>
requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_vec2_var(int h, T offset = 0) {
std::vector<std::vector<T>> v(h);
for (auto& row : v) {
int m;
std::cin >> m;
row = read_vec<T>(m, offset);
}
return v;
}
/**
* @brief 各行の最初に要素数が与えられる可変長2次元ベクターを標準入力から読み込む（非算術型用）
* @tparam T 要素の型
* @param h 行数
* @return 読み込んだ可変長の2次元ベクター
*/
template <typename T>
requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_vec2_var(int h) {
std::vector<std::vector<T>> v(h);
for (auto& row : v) {
int m;
std::cin >> m;
row = read_vec<T>(m);
}
return v;
}
/**
* @brief 1次元のペアのベクターを標準入力から読み込む
* @tparam T1 ペアの1つ目の要素の型 (デフォルト: int)
* @tparam T2 ペアの2つ目の要素の型 (デフォルト: int)
* @param n 要素数
* @param offset1 1つ目の要素から引く値 (デフォルト: 0)
* @param offset2 2つ目の要素から引く値 (デフォルト: 0)
* @return 読み込んだペアのベクター
*/
template <typename T1 = int, typename T2 = int>
inline std::vector<std::pair<T1, T2>> read_vec_pair(int n, T1 offset1 = 0, T2 offset2 = 0) {
std::vector<std::pair<T1, T2>> v(n);
for (auto& [x, y] : v) {
std::cin >> x >> y;
x -= offset1;
y -= offset2;
}
return v;
}
// ==================== 行列・三角形入力 ====================
/**
* @brief 上三角行列形式の入力を読み込み、2次元ベクターとして返す（算術型用、offset 付き）
* @tparam T 要素の型 (デフォルト: int)
* @param n 行列のサイズ (n x n)
* @param symmetric 対称行列にするかどうか (デフォルト: true)
* @param offset 読み込み時に値から引く量 (デフォルト: 0)
* @return 読み込んだ 2次元ベクター
*/
template <typename T = int>
requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_upper_tri(int n, bool symmetric = true, T offset = 0) {
std::vector<std::vector<T>> v(n, std::vector<T>(n));
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
std::cin >> v[i][j];
v[i][j] -= offset;
if (symmetric) v[j][i] = v[i][j];
}
}
return v;
}
/**
* @brief 上三角行列形式の入力を読み込み、2次元ベクターとして返す（非算術型用）
* @tparam T 要素の型
* @param n 行列のサイズ (n x n)
* @param symmetric 対称行列にするかどうか (デフォルト: true)
* @return 読み込んだ 2次元ベクター
*/
template <typename T>
requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_upper_tri(int n, bool symmetric = true) {
std::vector<std::vector<T>> v(n, std::vector<T>(n));
for (int i = 0; i < n - 1; ++i) {
for (int j = i + 1; j < n; ++j) {
std::cin >> v[i][j];
if (symmetric) v[j][i] = v[i][j];
}
}
return v;
}
/**
* @brief 下三角行列形式の入力を読み込み、2次元ベクターとして返す（算術型用、offset 付き）
* @tparam T 要素の型 (デフォルト: int)
* @param n 行列のサイズ (n x n)
* @param symmetric 対称行列にするかどうか (デフォルト: true)
* @param offset 読み込み時に値から引く量 (デフォルト: 0)
* @return 読み込んだ 2次元ベクター
*/
template <typename T = int>
requires std::is_arithmetic_v<T>
inline std::vector<std::vector<T>> read_lower_tri(int n, bool symmetric = true, T offset = 0) {
std::vector<std::vector<T>> v(n, std::vector<T>(n));
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
std::cin >> v[i][j];
v[i][j] -= offset;
if (symmetric) v[j][i] = v[i][j];
}
}
return v;
}
/**
* @brief 下三角行列形式の入力を読み込み、2次元ベクターとして返す（非算術型用）
* @tparam T 要素の型
* @param n 行列のサイズ (n x n)
* @param symmetric 对称行列にするかどうか (デフォルト: true)
* @return 読み込んだ 2次元ベクター
*/
template <typename T>
requires(!std::is_arithmetic_v<T>)
inline std::vector<std::vector<T>> read_lower_tri(int n, bool symmetric = true) {
std::vector<std::vector<T>> v(n, std::vector<T>(n));
for (int i = 1; i < n; ++i) {
for (int j = 0; j < i; ++j) {
std::cin >> v[i][j];
if (symmetric) v[j][i] = v[i][j];
}
}
return v;
}
// ==================== タプル入力 ====================
namespace detail {
/**
* @brief タプルの各要素を順番に読み込む（内部実装）
* @tparam Tuple タプル型
* @tparam Is インデックスのパック
* @param t 読み込み先のタプル
*/
template <typename Tuple, std::size_t... Is>
inline void read_tuple_impl(Tuple& t, std::index_sequence<Is...>) {
(std::cin >> ... >> std::get<Is>(t));
}
} // namespace detail
/**
* @brief 複数の型の値をまとめてタプルとして読み込む
* @tparam Ts 読み込む型のパック
* @return 読み込んだ値を格納した std::tuple<Ts...>
*
* 使い方:
* auto [a, b, c] = read_tuple<int, long long, std::string>();
*/
template <typename... Ts>
inline std::tuple<Ts...> read_tuple() {
std::tuple<Ts...> t;
detail::read_tuple_impl(t, std::index_sequence_for<Ts...>{});
return t;
}
/**
* @brief n 行分のタプルをベクターとして読み込む
* @tparam Ts 各行の型のパック
* @param n 行数
* @return 読み込んだ std::tuple<Ts...> の std::vector
*
* 使い方:
* auto v = read_vec_tuple<int, int, long long>(n);
* auto [a, b, c] = v[i];
*/
template <typename... Ts>
inline std::vector<std::tuple<Ts...>> read_vec_tuple(int n) {
std::vector<std::tuple<Ts...>> v(n);
for (auto& t : v)
detail::read_tuple_impl(t, std::index_sequence_for<Ts...>{});
return v;
}
// ==================== グラフ入力 ====================
/**
* @brief 無向グラフを辺リストから隣接リスト形式で読み込む
* @param n 頂点数
* @param m 辺数
* @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
* @return 0-indexed の隣接リスト (vector<vector<int>>)
*
* 使い方:
* auto g = read_graph(n, m, 1); // 1-indexed 入力
*/
inline std::vector<std::vector<int>> read_graph(int n, int m, int base = 1) {
std::vector<std::vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
u -= base;
v -= base;
g[u].push_back(v);
g[v].push_back(u);
}
return g;
}
/**
* @brief 有向グラフを辺リストから隣接リスト形式で読み込む
* @param n 頂点数
* @param m 辺数
* @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
* @return 0-indexed の隣接リスト (vector<vector<int>>)
*
* 使い方:
* auto g = read_digraph(n, m, 1); // 1-indexed 入力、u -> v の有向辺
*/
inline std::vector<std::vector<int>> read_digraph(int n, int m, int base = 1) {
std::vector<std::vector<int>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
std::cin >> u >> v;
u -= base;
v -= base;
g[u].push_back(v);
}
return g;
}
/**
* @brief 木を辺リストから隣接リスト形式で読み込む (n-1 辺)
* @param n 頂点数
* @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
* @return 0-indexed の隣接リスト (vector<vector<int>>)
*
* 使い方:
* auto g = read_tree(n, 1); // 1-indexed 入力
*/
inline std::vector<std::vector<int>> read_tree(int n, int base = 1) {
return read_graph(n, n - 1, base);
}
/**
* @brief 重み付き木を辺リストから隣接リスト形式で読み込む (n-1 辺)
* @tparam W 辺の重みの型
* @param n 頂点数
* @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
* @return 0-indexed の隣接リスト。各エントリは {隣接頂点, 重み} のペア
*
* 使い方:
* auto g = read_weighted_tree<long long>(n, 1);
*/
template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_tree(int n, int base = 1) {
return read_weighted_graph<W>(n, n - 1, base);
}
/**
* @brief 重み付き無向グラフを辺リストから隣接リスト形式で読み込む
* @tparam W 辺の重みの型
* @param n 頂点数
* @param m 辺数
* @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
* @return 0-indexed の隣接リスト。各エントリは {隣接頂点, 重み} のペア
*
* 使い方:
* auto g = read_weighted_graph<long long>(n, m, 1);
* for (auto [v, w] : g[u]) { ... }
*/
template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_graph(int n, int m, int base = 1) {
std::vector<std::vector<std::pair<int, W>>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
W w;
std::cin >> u >> v >> w;
u -= base;
v -= base;
g[u].emplace_back(v, w);
g[v].emplace_back(u, w);
}
return g;
}
/**
* @brief 重み付き有向グラフを辺リストから隣接リスト形式で読み込む
* @tparam W 辺の重みの型
* @param n 頂点数
* @param m 辺数
* @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
* @return 0-indexed の隣接リスト。各エントリは {隣接頂点, 重み} のペア
*
* 使い方:
* auto g = read_weighted_digraph<long long>(n, m, 1);
* for (auto [v, w] : g[u]) { ... }
*/
template <typename W>
inline std::vector<std::vector<std::pair<int, W>>> read_weighted_digraph(int n, int m, int base = 1) {
std::vector<std::vector<std::pair<int, W>>> g(n);
for (int i = 0; i < m; i++) {
int u, v;
W w;
std::cin >> u >> v >> w;
u -= base;
v -= base;
g[u].emplace_back(v, w);
}
return g;
}
// ==================== 辺リスト入力 ====================
/**
* @brief 無向/有向グラフの辺リストを読み込む
* @param m 辺数
* @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
* @return 0-indexed の辺リスト (std::vector<std::pair<int, int>>)
*/
inline std::vector<std::pair<int, int>> read_edges(int m, int base = 1) {
std::vector<std::pair<int, int>> edges(m);
for (int i = 0; i < m; ++i) {
int u, v;
std::cin >> u >> v;
edges[i] = {u - base, v - base};
}
return edges;
}
/**
* @brief 重み付き無向/有向グラフの辺リストを読み込む
* @tparam W 辺の重みの型
* @param m 辺数
* @param base 入力の頂点番号のベース (0-indexed なら 0、1-indexed なら 1)
* @return 0-indexed の重み付き辺リスト (std::vector<std::tuple<int, int, W>>)
*/
template <typename W>
inline std::vector<std::tuple<int, int, W>> read_weighted_edges(int m, int base = 1) {
std::vector<std::tuple<int, int, W>> edges(m);
for (int i = 0; i < m; ++i) {
int u, v;
W w;
std::cin >> u >> v >> w;
edges[i] = {u - base, v - base, w};
}
return edges;
}
#include <algorithm>
#include <concepts>
#include <numeric>
#include <print>
#include <vector>
#include <tuple>
/**
* @brief aをaとbの最小値で更新
* @param a 更新対象
* @param b 比較値
* @return 更新されたらtrue
*/
template <typename T, typename U>
inline bool chmin(T& a, const U& b) {
if (a > b) {
a = b;
return true;
}
return false;
}
/**
* @brief aをaとbの最大値で更新
* @param a 更新対象
* @param b 比較値
* @return 更新されたらtrue
*/
template <typename T, typename U>
inline bool chmax(T& a, const U& b) {
if (a < b) {
a = b;
return true;
}
return false;
}
/**
* @brief 整数除算の切り上げ (b>0)
* @param a 分子
* @param b 分母
* @return 切り上げ値
*/
template <std::integral T>
inline T div_ceil(T a, T b) {
if (a >= 0) return (a + b - 1) / b;
return a / b;
}
/**
* @brief 整数除算の切り捨て (b>0)
* @param a 分子
* @param b 分母
* @return 切り捨て値
*/
template <std::integral T>
inline T div_floor(T a, T b) {
if (a >= 0) return a / b;
return (a - b + 1) / b;
}
/**
* @brief 連続整数のvector生成
* @param n 要素数
* @param start 開始値(デフォルト0)
* @return 生成されたvector
*/
template <typename T = int>
inline std::vector<T> iota_vec(int n, T start = 0) {
std::vector<T> v(n);
std::iota(v.begin(), v.end(), start);
return v;
}
namespace internal {
/**
* @brief 多次元のstd::vectorをデフォルト値で生成するヘルパー
*/
template <typename T, typename... Args>
inline auto make_vec_default(int n, Args... args) {
if constexpr (sizeof...(args) == 0) {
return std::vector<T>(n);
} else {
return std::vector(n, make_vec_default<T>(args...));
}
}
} // namespace internal
/**
* @brief 多次元のstd::vectorを初期値付きで生成する
* @param n サイズ
* @param init 初期値
* @return 1次元のstd::vector
*/
template <typename T>
inline std::vector<T> make_vec(int n, const T& init) {
return std::vector<T>(n, init);
}
/**
* @brief 多次元のstd::vectorを初期値付きで生成する（再帰・推論）
* @param n 最初の次元のサイズ
* @param args 残りの次元のサイズ、および最終的な初期値
* @return 多次元のstd::vector
*/
template <typename... Args>
inline auto make_vec(int n, Args... args) {
return std::vector(n, make_vec(args...));
}
/**
* @brief 多次元のstd::vectorをデフォルト値で生成する
* @tparam T 要素の型
* @param args 次元のサイズ列
* @return 多次元のstd::vector
*/
template <typename T, typename... Args>
inline auto make_vec(Args... args) {
return internal::make_vec_default<T>(args...);
}
/**
* @brief 同じサイズの複数の多次元のstd::vectorを生成する
* @tparam Ts 各vectorの要素型
* @param args 次元のサイズ列
* @return 生成された各テーブルを格納したstd::tuple
*/
template <typename... Ts, typename... Args>
inline auto make_vecs(Args... args) {
return std::make_tuple(internal::make_vec_default<Ts>(args...)...);
}
/**
* @brief vectorを2回反復連結
* @param v 元のvector
* @return 2倍長のvector
*/
template <typename T>
inline std::vector<T> doubled(const std::vector<T>& v) {
std::vector<T> res;
res.reserve(v.size() * 2);
res.insert(res.end(), v.begin(), v.end());
res.insert(res.end(), v.begin(), v.end());
return res;
}
/**
* @brief 区間[l1,r1)と[l2,r2)の共通長
* @param l1 区間1左端
* @param r1 区間1右端
* @param l2 区間2左端
* @param r2 区間2右端
* @return 共通部分の長さ(ない場合は0)
*/
template <typename T>
inline T overlap_length(T l1, T r1, T l2, T r2) {
return std::max(static_cast<T>(0), std::min(r1, r2) - std::max(l1, l2));
}
/**
* @brief "Yes"/"No"を出力
* @param b trueでYes, falseでNo
*/
inline void Yes(bool b = true) {
std::println("{}", (b ? "Yes" : "No"));
}
/**
* @brief "No"を出力
*/
inline void No() {
std::println("No");
}
#ifdef LOCAL
#include <library/my_library/utility/debug.hpp>
#else
#define debug(...)
#endif
using namespace std;
namespace rv = std::views; // NOLINT
using lint = long long;
#define ALL(a) (a).begin(), (a).end()
// [TEMPLATE_END]
#include <algorithm>
#include <chrono>
#include <cstdint>
#include <numeric>
#include <random>
#include <vector>
namespace prime {
/**
* @brief 素数・約数ライブラリ
*
* ◆ 素数判定
* is_prime_mr(n) Miller-Rabin (64bit対応, 決定的)
*
* ◆ 素因数分解
* factorize(n) 試し割り法 O(√N)
* factorize_fast(n) Pollard's Rho O(N^{1/4})
*
* ◆ 約数列挙
* divisors(n) O(√N)
*
* ◆ 篩 (前処理ベース)
* Eratosthenes sieve(n) エラトステネスの篩
* sieve.is_prime(x) / sieve.primes() / sieve.factorize(x) / sieve.divisors(x)
* LinearSieve sieve(n) 線形篩 (φ, μ 付き)
* sieve.is_prime(x) / sieve.primes / sieve.phi / sieve.mobius / sieve.factorize(x)
*
* ◆ 区間篩
* segment_sieve(L, R) [L, R] の素数リスト
* segment_sieve_bool(L, R) [L, R] の素数判定テーブル
* count_primes_range(L, R) [L, R] の素数の個数
*
* ◆ ユーティリティ
* prime_count_table(n) i 以下の素数の個数テーブル
* distinct_prime_factor_count_table(n) 互いに異なる素因数の個数テーブル (ω(n))
* total_prime_factor_count_table(n) 素因数の総数テーブル (Ω(n))
* euler_phi(n) オイラーのφ関数 (単発)
*/
// ============================================================
// 内部ユーティリティ
// ============================================================
namespace internal {
/**
* @brief オーバーフロー安全な mod 乗算
* @param a 乗算する値
* @param b 乗算する値
* @param mod 法
* @return a * b mod mod
*/
inline long long mod_mul(long long a, long long b, long long mod) { return (__int128)a * b % mod; }
/**
* @brief mod べき乗
* @param base 底
* @param exp 指数
* @param mod 法
* @return base^exp mod mod
*/
inline long long mod_pow(long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = mod_mul(result, base, mod);
base = mod_mul(base, base, mod);
exp >>= 1;
}
return result;
}
} // namespace internal
// ============================================================
// 素数判定
// ============================================================
/**
* @brief Miller-Rabin 素数判定 (64bit対応)
*
* 決定的判定。2^63 未満の全ての整数に対して正しく判定する。
*
* @param n 判定する数
* @return 素数なら true
*/
inline bool is_prime_mr(long long n) {
if (n < 2) return false;
if (n == 2 || n == 3) return true;
if (n % 2 == 0) return false;
long long d = n - 1;
int r = 0;
while (d % 2 == 0) {
d /= 2;
r++;
}
auto mod_pow = [](long long base, long long exp, long long mod) {
long long result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = (__int128)result * base % mod;
base = (__int128)base * base % mod;
exp >>= 1;
}
return result;
};
// 決定的テスト用の証拠
static const std::vector<long long> witnesses = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
for (long long a : witnesses) {
if (a >= n) continue;
long long x = mod_pow(a, d, n);
if (x == 1 || x == n - 1) continue;
bool composite = true;
for (int i = 0; i < r - 1; i++) {
x = (__int128)x * x % n;
if (x == n - 1) {
composite = false;
break;
}
}
if (composite) return false;
}
return true;
}
// ============================================================
// 素因数分解
// ============================================================
/**
* @brief 素因数分解 (試し割り法)
*
* 計算量: O(√N)
*
* @param n 素因数分解する数
* @return (素因数, 指数) のペアの配列
*/
inline std::vector<std::pair<long long, int>> factorize(long long n) {
std::vector<std::pair<long long, int>> result;
for (long long p = 2; p * p <= n; p++) {
if (n % p == 0) {
int cnt = 0;
while (n % p == 0) {
n /= p;
cnt++;
}
result.emplace_back(p, cnt);
}
}
if (n > 1) result.emplace_back(n, 1);
return result;
}
namespace internal {
/**
* @brief Pollard's rho アルゴリズム (Brent 変法)
*
* n の非自明な因数を1つ返す。
* n が偶数なら 2 を返し、素数なら n 自身を返す。
*
* @param n 因数を求める合成数 (n >= 2)
* @return n の非自明な因数
*/
inline long long pollard_rho(long long n) {
if (n % 2 == 0) return 2;
if (is_prime_mr(n)) return n;
static std::mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
while (true) {
long long c = rng() % (n - 1) + 1;
auto f = [&](long long x) { return (mod_mul(x, x, n) + c) % n; };
long long x = rng() % (n - 2) + 2;
long long y = x;
long long g = 1;
// Brent の周期検出 + GCD バッチング
while (g == 1) {
long long ys = y;
long long q = 1;
constexpr int batch = 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 += batch) {
ys = y;
int bound = std::min(batch, r - k);
for (int i = 0; i < bound; i++) {
y = f(y);
q = mod_mul(q, std::abs(x - y), n);
}
g = std::gcd(q, n);
}
}
// バッチングで g == n になった場合、1ステップずつ再試行
if (g == n) {
g = 1;
while (g == 1) {
ys = f(ys);
g = std::gcd(std::abs(x - ys), n);
}
}
}
if (g != n) return g;
}
}
/**
* @brief 再帰的に素因数を収集する内部関数
* @param n 素因数分解する数
* @param result 素因数を追加するベクタ
*/
inline void collect_factors(long long n, std::vector<long long>& result) {
if (n <= 1) return;
if (is_prime_mr(n)) {
result.push_back(n);
return;
}
long long d = pollard_rho(n);
collect_factors(d, result);
collect_factors(n / d, result);
}
} // namespace internal
/**
* @brief 高速素因数分解 (Miller-Rabin + Pollard's Rho)
*
* 期待計算量 O(N^{1/4} polylog N)
* 試し割り法 (O(√N)) より大幅に高速。
* N ≤ 9×10^18 程度まで対応。
*
* @param n 素因数分解する数
* @return (素因数, 指数) のペアの配列 (素因数の昇順)
*
* @example
* auto factors = prime::factorize_fast(1000000007LL * 998244353LL);
* // => {{998244353, 1}, {1000000007, 1}}
*/
inline std::vector<std::pair<long long, int>> factorize_fast(long long n) {
std::vector<long long> primes;
internal::collect_factors(n, primes);
std::sort(primes.begin(), primes.end());
std::vector<std::pair<long long, int>> result;
for (long long p : primes) {
if (!result.empty() && result.back().first == p) {
result.back().second++;
} else {
result.emplace_back(p, 1);
}
}
return result;
}
// ============================================================
// 約数列挙
// ============================================================
/**
* @brief 約数列挙
*
* 計算量: O(√N)
*
* @param n 約数を列挙する数
* @return 約数の配列 (昇順)
*/
inline std::vector<long long> divisors(long long n) {
std::vector<long long> small, large;
for (long long i = 1; i * i <= n; i++) {
if (n % i == 0) {
small.push_back(i);
if (i != n / i) large.push_back(n / i);
}
}
for (int i = (int)large.size() - 1; i >= 0; i--) small.push_back(large[i]);
return small;
}
// ============================================================
// 篩 (前処理ベース)
// ============================================================
/**
* @brief エラトステネスの篩
*
* 計算量: O(N log log N) 前処理
* 素数列挙・素数判定・高速素因数分解・約数列挙を提供する。
*
* @example
* Eratosthenes sieve(1000000);
* sieve.is_prime(997); // true
* sieve.primes(); // {2, 3, 5, 7, 11, ...}
* sieve.factorize(360); // {{2,3}, {3,2}, {5,1}}
*/
struct Eratosthenes {
std::vector<bool> is_prime_table;
std::vector<int> prime_list;
std::vector<int> min_factor; // 最小の素因数
explicit Eratosthenes(int n) : is_prime_table(n + 1, true), min_factor(n + 1, 0) {
is_prime_table[0] = is_prime_table[1] = false;
min_factor[1] = 1;
for (int i = 2; i <= n; i++) {
if (is_prime_table[i]) {
prime_list.push_back(i);
min_factor[i] = i;
for (long long j = (long long)i * i; j <= n; j += i) {
is_prime_table[j] = false;
if (min_factor[j] == 0) min_factor[j] = i;
}
}
}
}
bool is_prime(int n) const { return is_prime_table[n]; }
const std::vector<int>& primes() const { return prime_list; }
/**
* @brief 高速な素因数分解 (前処理済みの範囲内)
* @param n 素因数分解する数
* @return (素因数, 指数) のペアの配列
*/
std::vector<std::pair<int, int>> factorize(int n) const {
std::vector<std::pair<int, int>> result;
while (n > 1) {
int p = min_factor[n];
int cnt = 0;
while (min_factor[n] == p) {
n /= p;
cnt++;
}
result.emplace_back(p, cnt);
}
return result;
}
/**
* @brief 約数列挙
* @param n 約数を列挙する数
* @return 約数の配列
*/
std::vector<int> divisors(int n) const {
std::vector<int> result = {1};
for (auto [p, e] : factorize(n)) {
int sz = result.size();
int pw = 1;
for (int i = 0; i < e; i++) {
pw *= p;
for (int j = 0; j < sz; j++) {
result.push_back(result[j] * pw);
}
}
}
return result;
}
};
/**
* @brief 線形篩 (各合成数を最小素因数で1回だけ篩う)
*
* 計算量: 厳密 O(N)
* エラトステネスより定数倍が重いが、乗法的関数 (オイラーφ, メビウスμ) も同時に計算可能。
*
* @example
* LinearSieve sieve(100000);
* auto& primes = sieve.primes;
* int phi_10 = sieve.phi[10]; // オイラーのφ関数
*/
struct LinearSieve {
std::vector<int> primes;
std::vector<int> min_factor; // 最小素因数
std::vector<int> phi; // オイラーのφ関数
std::vector<int> mobius; // メビウス関数
explicit LinearSieve(int n) : min_factor(n + 1, 0), phi(n + 1), mobius(n + 1) {
phi[1] = 1;
mobius[1] = 1;
for (int i = 2; i <= n; i++) {
if (min_factor[i] == 0) {
// i は素数
primes.push_back(i);
min_factor[i] = i;
phi[i] = i - 1;
mobius[i] = -1;
}
for (int p : primes) {
if ((long long)p * i > n) break;
min_factor[p * i] = p;
if (i % p == 0) {
// p は i の素因数
phi[p * i] = phi[i] * p;
mobius[p * i] = 0;
break;
} else {
// p は i と互いに素
phi[p * i] = phi[i] * (p - 1);
mobius[p * i] = -mobius[i];
}
}
}
}
bool is_prime(int n) const { return n >= 2 && min_factor[n] == n; }
/**
* @brief 高速な素因数分解
* @param n 素因数分解する数
* @return (素因数, 指数) のペアの配列
*/
std::vector<std::pair<int, int>> factorize(int n) const {
std::vector<std::pair<int, int>> result;
while (n > 1) {
int p = min_factor[n];
int cnt = 0;
while (n % p == 0) {
n /= p;
cnt++;
}
result.emplace_back(p, cnt);
}
return result;
}
};
// ============================================================
// 区間篩 (Segmented Sieve)
// ============================================================
/**
* @brief 区間篩：[L, R] 範囲の素数を列挙
*
* 事前に sqrt(R) までの素数を用意し、[L, R] を篩う。
* 計算量: O(sqrt(R) + (R - L) log log R)
*
* @param L 下限
* @param R 上限
* @return [L, R] 範囲の素数の配列
*
* @example
* auto primes = segment_sieve(1000000000000LL, 1000000001000LL);
*/
inline std::vector<long long> segment_sieve(long long L, long long R) {
if (L < 2) L = 2;
if (R < L) return {};
// sqrt(R) までの素数を用意
long long sqrtR = 1;
while (sqrtR * sqrtR <= R) sqrtR++;
Eratosthenes sieve(sqrtR);
const auto& small_primes = sieve.primes();
// [L, R] の篩
std::vector<bool> is_prime(R - L + 1, true);
for (int p : small_primes) {
// L 以上で p の倍数である最小の数
long long start = ((L + p - 1) / p) * p;
if (start == p) start += p; // p 自身は除外しない
for (long long j = start; j <= R; j += p) {
is_prime[j - L] = false;
}
}
std::vector<long long> result;
for (long long i = L; i <= R; i++) {
if (is_prime[i - L]) result.push_back(i);
}
return result;
}
/**
* @brief 区間篩：[L, R] の各数が素数かどうかのbool配列を返す
* @param L 下限
* @param R 上限
* @return [L, R] の各数が素数かどうかの bool 配列 (インデックス0がL)
*/
inline std::vector<bool> segment_sieve_bool(long long L, long long R) {
if (R < L) return {};
std::vector<bool> result(R - L + 1, true);
if (L < 2) {
if (L == 0) {
if (R >= 0) result[0] = false;
if (R >= 1) result[1] = false;
} else if (L == 1) {
result[0] = false;
}
}
long long sqrtR = 1;
while (sqrtR * sqrtR <= R) sqrtR++;
Eratosthenes sieve(sqrtR);
const auto& small_primes = sieve.primes();
for (int p : small_primes) {
long long start = std::max(2LL, (L + p - 1) / p) * p;
for (long long j = start; j <= R; j += p) {
result[j - L] = false;
}
}
return result;
}
/**
* @brief [L, R] の素数の個数をカウント
* @param L 下限
* @param R 上限
* @return 素数の個数
*/
inline long long count_primes_range(long long L, long long R) {
auto primes = segment_sieve(L, R);
return primes.size();
}
// ============================================================
// ユーティリティ
// ============================================================
/**
* @brief 各数がいくつの互いに異なる素因数を持つかのテーブル (omega数)
*
* 計算量: O(N log log N)
* 例えば 12 = 2^2 * 3 の場合、異なる素因数は 2, 3 の 2 つなので 2 を返す。
*
* @param n 上限
* @return 各数iが持つ異なる素因数の個数を格納した配列 (サイズ n + 1)
*/
inline std::vector<int> distinct_prime_factor_count_table(int n) {
if (n < 0) return {};
std::vector<int> count(n + 1, 0);
for (int i = 2; i <= n; i++) {
if (count[i] == 0) {
for (int j = i; j <= n; j += i) {
count[j]++;
}
}
}
return count;
}
/**
* @brief 各数がいくつの素因数を持つかのテーブル (Omega数、多重度込み)
*
* 計算量: O(N log log N)
* 例えば 12 = 2^2 * 3 の場合、素因数は 2, 2, 3 の 3 つなので 3 を返す。
*
* @param n 上限
* @return 各数iが持つ素因数(重複込み)の個数を格納した配列 (サイズ n + 1)
*/
inline std::vector<int> total_prime_factor_count_table(int n) {
if (n < 0) return {};
std::vector<int> count(n + 1, 0);
std::vector<int> min_factor(n + 1, 0);
for (int i = 2; i <= n; i++) {
if (min_factor[i] == 0) {
for (int j = i; j <= n; j += i) {
if (min_factor[j] == 0) min_factor[j] = i;
}
}
count[i] = count[i / min_factor[i]] + 1;
}
return count;
}
/**
* @brief n 以下の素数の個数 (簡易版、O(N) 前処理)
* @param n 上限
* @return 各数i以下の素数の個数を格納した配列
*/
inline std::vector<int> prime_count_table(int n) {
std::vector<bool> is_prime(n + 1, true);
std::vector<int> cnt(n + 1, 0);
is_prime[0] = is_prime[1] = false;
for (int i = 2; i <= n; i++) {
if (is_prime[i]) {
for (int j = i * 2; j <= n; j += i) is_prime[j] = false;
}
cnt[i] = cnt[i - 1] + is_prime[i];
}
return cnt;
}
/**
* @brief n のオイラーのφ関数 (単発計算用)
* @param n 値
* @return オイラーのφ関数値
*/
inline long long euler_phi(long long n) {
long long result = n;
for (long long p = 2; p * p <= n; p++) {
if (n % p == 0) {
while (n % p == 0) n /= p;
result -= result / p;
}
}
if (n > 1) result -= result / n;
return result;
}
} // namespace prime
void solve() {
// Write your code here
lint L, R;
scan(L, R);
if (L % 2 == 0) L++;
for (lint p = L; p <= R; p += 2) {
auto vec = prime::factorize_fast(p);
debug(vec);
if (ssize(vec) == 3 && vec[0].second == 2 && vec[1].second == 1 && vec[2].second == 1) {
println("{}", p);
return;
}
}
println("{}", -1);
}
int main() {
fast_io();
solve();
}