#1154280 (C++23) No.3485 Find 495-like Number

• 問題: No.3485 Find 495-like Number
• ユーザー: houren
• 提出日時: 2026-03-27 22:48:49
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: WA
• 実行時間: -
• コード長: 5,684 bytes
• コンパイル時間: 3,616 ms
• コンパイル使用メモリ: 342,844 KB
• 実行使用メモリ: 8,588 KB
• 最終ジャッジ日時: 2026-03-27 22:49:17
• 合計ジャッジ時間: 15,404 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
// https://drken1215.hatenablog.com/entry/2023/05/23/233000#chap5
// 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;

// Miller-Rabin
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 < 4759123141LL)
        return MillerRabin(N, {2, 7, 61});
    else
        return MillerRabin(N, {2, 325, 9375, 28178, 450775, 9780504, 1795265022});
}
using ll = long long;
#define rep(i, n) for(int i = 0; i < n; ++i)
struct PrimeNumber{
    vector<int> _PN;
    vector<bool> _B;
    int n;
    PrimeNumber(int _n=0){
        init(_n);
    }
    void init(int _n){
        n = _n;
        _B.assign(n+1,true);
        _B[1] = false;
        for(int i=2;i<=n;i++){
            if(_B[i]){
                _PN.push_back(i);
                for(ll j=(ll)i*i;j<=n;j+=i) _B[j] = false;
            }
        }
    }
    vector<int> pnlist(){ return _PN; };
};

int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    PrimeNumber _(7500000);
    auto pn = _.pnlist();
    int n = pn.size();
    ll l,r;
    cin >> l >> r;
    bool f = true;
    for(int i=1;f;++i){
        for(int j=i+1;j<n;++j){
            ll x = ll(pn[i])*pn[i]*pn[j];
            ll l2 = (l+x-1)/x, r2 = r/x;
            l2 = max<ll>(l2,pn[j+1]);
            if(l2>r2){
                if(j==i+1) f = false;
                break;
            }
            while(l2%6!=1&&l2%6!=5)++l2;
            if(l2%6==1){
                for(;l2<=r2;l2+=6){
                    if(is_prime(l2)){
                        cout << x*l2 << '\n';
                        return 0;
                    }
                    if(l2+4<=r2 && is_prime(l2+4)){
                        cout << x*(l2+4) << '\n';
                        return 0;
                    }
                }
            }else{
                for(;l2<=r2;l2+=6){
                    if(is_prime(l2)){
                        cout << x*l2 << '\n';
                        return 0;
                    }
                    if(l2+2<=r2 && is_prime(l2+2)){
                        cout << x*(l2+2) << '\n';
                        return 0;
                    }
                }
            }
        }
    }
    cout << "-1\n";
    return 0;
}