結果

問題 No.3485 Find 495-like Number
コンテスト
ユーザー kwm_t
提出日時 2026-11-01 18:50:23
言語 C++23
(gcc 15.3.0 + boost 1.92.0 + ACL)
コンパイル:
g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
WA  
実行時間 -
コード長 7,424 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 2,477 ms
コンパイル使用メモリ 353,852 KB
実行使用メモリ 9,908 KB
最終ジャッジ日時 2026-11-01 18:50:35
合計ジャッジ時間 8,929 ms
ジャッジサーバーID
（参考情報） 		judge7_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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 sieve.hpp
 * @brief 篩による素数列挙
 * @author kwm_t
 * @see https://github.com/kwm-t/cp-library/blob/main/math/sieve.hpp
 */
#ifndef KWM_T_MATH_SIEVE_HPP
#define KWM_T_MATH_SIEVE_HPP

#include <vector>

namespace kwm_t::math {

/**
 * @brief エラトステネスの篩（bool版）
 * is_prime[i] を返す
 */
inline std::vector<bool> sieve(int n) {
	std::vector<bool> is_prime(n + 1, true);

	if (n >= 0) is_prime[0] = false;
	if (n >= 1) is_prime[1] = false;

	for (int p = 2; p * p <= n; ++p) {
		if (!is_prime[p]) continue;
		for (int i = p * p; i <= n; i += p) {
			is_prime[i] = false;
		}
	}
	return is_prime;
}

/**
 * @brief 素数列挙
 * sieve を利用して primes を返す
 */
inline std::vector<int> primes(int n) {
	auto is_prime = sieve(n);
	std::vector<int> res;

	for (int i = 2; i <= n; ++i) {
		if (is_prime[i]) res.push_back(i);
	}
	return res;
}

/**
 * @brief 区間篩
 * [l, r) に含まれる素数を列挙する
 */
inline std::vector<long long> segmented_sieve(long long l, long long r) {
	std::vector<long long> res;
	if (r <= 2 || l >= r) return res;

	l = std::max(l, 2LL);

	long long n = static_cast<long long>(std::sqrt(r - 1)) + 1;
	auto is_prime = sieve(static_cast<int>(n));

	std::vector<bool> ok(r - l, true);

	for (long long p = 2; p <= n; ++p) {
		if (!is_prime[p]) continue;

		long long start = std::max(p * p, ((l + p - 1) / p) * p);
		for (long long i = start; i < r; i += p) {
			ok[i - l] = false;
		}
	}

	for (long long i = 0; i < r - l; ++i) {
		if (ok[i]) res.push_back(l + i);
	}
	return res;
}
}

#endif


/**
 * @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);
	long long l, r; cin >> l >> r;
	r = min(l + 45000, r);
	int width = r - l + 1;
	auto ps = kwm_t::math::segmented_sieve(l / 45, r / 45 + 10);
	set<long long>pst;
	for (auto e : ps)pst.insert(e);
	kwm_t::math::PollardRho pr;
	for (long long i = l; i <= r; ++i) {
		auto ps = pr.factor(i);
		if (ps.size() != 4)continue;
		if (ps[0] == 2)continue;
		if (ps[0] != ps[1])continue;
		if (ps[1] == ps[2])continue;
		if (ps[2] == ps[3])continue;
		cout << i << endl;
		return 0;
		//if (i % 45)continue;
		//long long j = i / 45;
		//if (j == 2 || j == 3 || j == 5)continue;
		//if (pst.count(j)) {
		//	cout << i << endl;
		//	return 0;
		//}
	}
	cout << -1 << endl;
	return 0;
}
0