結果
| 問題 | No.3485 Find 495-like Number |
| コンテスト | |
| ユーザー |
👑  binap
|
| 提出日時 | 2026-02-27 08:00:41 |
| 言語 | C++17 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
AC
|
| 実行時間 | 13 ms / 5,000 ms |
| コード長 | 7,465 bytes |
| 記録 | |
| コンパイル時間 | 4,780 ms |
| コンパイル使用メモリ | 280,316 KB |
| 実行使用メモリ | 6,272 KB |
| 最終ジャッジ日時 | 2026-03-27 20:58:37 |
| 合計ジャッジ時間 | 13,868 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 34 |
ソースコード
#include<bits/stdc++.h>
#include<atcoder/all>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
using namespace atcoder;
typedef long long ll;
typedef pair<int, int> P;
template <int m> ostream& operator<<(ostream& os, const static_modint<m>& a) {os << a.val(); return os;}
template <int m> ostream& operator<<(ostream& os, const dynamic_modint<m>& a) {os << a.val(); return os;}
template <int m> istream& operator>>(istream& is, static_modint<m>& a) {long long x; is >> x; a = x; return is;}
template <int m> istream& operator>>(istream& is, dynamic_modint<m>& a) {long long x; is >> x; a = x; return is;}
template<typename T> istream& operator>>(istream& is, vector<T>& v){int n = v.size(); assert(n > 0); rep(i, n) is >> v[i]; return is;}
template<typename U, typename T> ostream& operator<<(ostream& os, const pair<U, T>& p){os << p.first << ' ' << p.second; return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> ostream& operator<<(ostream& os, const vector<vector<T>>& v){int n = v.size(); rep(i, n) os << v[i] << (i == n - 1 ? "\n" : ""); return os;}
template<typename T> ostream& operator<<(ostream& os, const set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename T> ostream& operator<<(ostream& os, const unordered_set<T>& se){for(T x : se) os << x << " "; os << "\n"; return os;}
template<typename S, auto op, auto e> ostream& operator<<(ostream& os, const atcoder::segtree<S, op, e>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename S, auto op, auto e, typename F, auto mapping, auto composition, auto id> ostream& operator<<(ostream& os, const atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>& seg){int n = seg.max_right(0, [](S){return true;}); rep(i, n) os << seg.get(i) << (i == n - 1 ? "\n" : " "); return os;}
template<typename T> void chmin(T& a, T b){a = min(a, b);}
template<typename T> void chmax(T& a, T b){a = max(a, b);}
// montgomery modint (MOD < 2^62, MOD is odd)
struct MontgomeryModInt64 {
using mint = MontgomeryModInt64;
using u64 = uint64_t;
using u128 = __uint128_t;
// static menber
static u64 MOD;
static u64 INV_MOD; // INV_MOD * MOD ≡ 1 (mod 2^64)
static u64 T128; // 2^128 (mod MOD)
// inner value
u64 val;
// constructor
MontgomeryModInt64() : val(0) { }
MontgomeryModInt64(long long v) : val(reduce((u128(v) + MOD) * T128)) { }
u64 get() const {
u64 res = reduce(val);
return res >= MOD ? res - MOD : res;
}
// mod getter and setter
static u64 get_mod() { return MOD; }
static void set_mod(u64 mod) {
assert(mod < (1LL << 62));
assert((mod & 1));
MOD = mod;
T128 = -u128(mod) % mod;
INV_MOD = get_inv_mod();
}
static u64 get_inv_mod() {
u64 res = MOD;
for (int i = 0; i < 5; ++i) res *= 2 - MOD * res;
return res;
}
static u64 reduce(const u128 &v) {
return (v + u128(u64(v) * u64(-INV_MOD)) * MOD) >> 64;
}
// arithmetic operators
mint operator - () const { return mint() - mint(*this); }
mint operator + (const mint &r) const { return mint(*this) += r; }
mint operator - (const mint &r) const { return mint(*this) -= r; }
mint operator * (const mint &r) const { return mint(*this) *= r; }
mint operator / (const mint &r) const { return mint(*this) /= r; }
mint& operator += (const mint &r) {
if ((val += r.val) >= 2 * MOD) val -= 2 * MOD;
return *this;
}
mint& operator -= (const mint &r) {
if ((val += 2 * MOD - r.val) >= 2 * MOD) val -= 2 * MOD;
return *this;
}
mint& operator *= (const mint &r) {
val = reduce(u128(val) * r.val);
return *this;
}
mint& operator /= (const mint &r) {
*this *= r.inv();
return *this;
}
mint inv() const { return pow(MOD - 2); }
mint pow(u128 n) const {
mint res(1), mul(*this);
while (n > 0) {
if (n & 1) res *= mul;
mul *= mul;
n >>= 1;
}
return res;
}
// other operators
bool operator == (const mint &r) const {
return (val >= MOD ? val - MOD : val) == (r.val >= MOD ? r.val - MOD : r.val);
}
bool operator != (const mint &r) const {
return (val >= MOD ? val - MOD : val) != (r.val >= MOD ? r.val - MOD : r.val);
}
friend istream& operator >> (istream &is, mint &x) {
long long t;
is >> t;
x = mint(t);
return is;
}
friend ostream& operator << (ostream &os, const mint &x) {
return os << x.get();
}
friend mint modpow(const mint &r, long long n) {
return r.pow(n);
}
friend mint modinv(const mint &r) {
return r.inv();
}
};
typename MontgomeryModInt64::u64
MontgomeryModInt64::MOD, MontgomeryModInt64::INV_MOD, MontgomeryModInt64::T128;
template<typename T>
T pow_mod(T A, T N, T MOD){
T res = 1 % MOD;
A %= MOD;
while(N){
if(N & 1) res = (res * A) % MOD;
A = (A * A) % MOD;
N >>= 1;
}
return res;
}
bool MillerRabin(long long N, vector<long long> A){
using mint = MontgomeryModInt64;
mint::set_mod(N);
long long s = 0, d = N - 1;
while(d % 2 == 0){
s++;
d >>= 1;
}
for(auto a : A){
if(N <= a) return true;
mint x = mint(a).pow(d);
if(x != 1){
long long t;
for(t = 0; t < s; t++){
if(x == N - 1) break;
x *= x;
}
if(t == s) return false;
}
}
return true;
};
bool is_prime(long long N){
if(N <= 1) return false;
if(N == 2) return true;
if(N % 2 == 0) return false;
if(N < 4759123141LL) return MillerRabin(N, {2, 7, 61});
else return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
};
vector<long long> prime_factor(long long N){
assert(N >= 1);
using u128 = __uint128_t;
vector<long long> res;
vector<long long> calc;
while(N % 2 == 0){
N /= 2;
res.push_back(2);
}
if(N == 1) return res;
calc.push_back(N);
while(calc.size()){
long long N = calc.back(); calc.pop_back();
long long x, y, c, g;
auto f = [&](long long x){return (u128(x) * x + c) % N;};
while(!is_prime(N)){
x = rand() % N; y = x;
c = (rand() % (N - 1)) + 1;
g = 1;
while(g == 1){
x = f(x);
y = f(f(y));
g = gcd(abs(x - y), N);
}
if(g == N) continue;
if(is_prime(N / g)) res.push_back(N / g);
else calc.push_back(N / g);
N = g;
}
res.push_back(N);
}
return res;
};
long long find_primitive_root(long long P){
assert(is_prime(P));
vector<long long> primes = prime_factor(P - 1);
sort(primes.begin(), primes.end());
primes.erase(unique(primes.begin(), primes.end()), primes.end());
long long g;
while(true){
g = rand() % (P - 1) + 1;
bool success = true;
for(auto p : primes){
if((long long)pow_mod<__uint128_t>(g, (P - 1) / p, P) == 1) success = false;
}
if(success) return g;
}
};
int main(){
long long l, r;
cin >> l >> r;
if(r - l >= 45000) r = l + 45000;
for(long long x = l; x <= r; x++){
auto g = prime_factor(x);
sort(g.begin(), g.end());
if(g.size() == 4 and g[0] != 2 and g[0] == g[1] and g[1] != g[2] and g[2] != g[3]){
cout << x << "\n";
return 0;
}
}
cout << "-1\n";
return 0;
}