#1154154 (C++17) No.3485 Find 495-like Number

• 問題: No.3485 Find 495-like Number
• ユーザー: GOTKAKO
• 提出日時: 2026-03-27 22:11:05
• 言語: C++17 (gcc 15.2.0 + boost 1.89.0)
• 結果: AC
• 実行時間: 147 ms / 5,000 ms
• コード長: 3,972 bytes
• コンパイル時間: 2,079 ms
• コンパイル使用メモリ: 217,124 KB
• 実行使用メモリ: 6,272 KB
• 最終ジャッジ日時: 2026-03-27 22:11:20
• 合計ジャッジ時間: 10,378 ms
• ジャッジサーバーID （参考情報）: judge3_0 / judge2_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;

template<int idx>
struct Montgomery{
    //2^62未満&奇数modのみ.
    //初めにsetmodする.
    using u64 = uint64_t;
    using u128 = __uint128_t;
 
    private:
    static u64 mod,N2,Rsq; //N*N2≡1(mod N);
    //Rsq = R^2modN; R=2^64.
    u64 v = 0;
    public:
    long long val()const{return reduce(v);}
    static constexpr u64 getmod(){return mod;}
    static void setmod(u64 m){
        assert(m<(1LL<<62)&&(m&1));
        mod = m; N2 = mod;
        for(int i=0; i<5; i++) N2 *= 2-N2*mod;
        Rsq = (-u128(mod))%mod;
    }
    //reduce = T*R^-1modNを求める.
    u64 reduce(const u128 &T)const{
        //T*R^-1≡(T+(T*(-N2))modR*N)/R 2N未満なので-N必要かだけで良い.
        u64 ret = (T+u128(((u64)T)*(-N2))*mod)>>64;
        if(ret >= mod) ret -= mod;
        return ret;
    }
    //初期値<mod. 初めにw*R modN...->reduce(R^2)でok.
    Montgomery(){v = 0;} Montgomery(long long w):v(reduce(u128(w)*Rsq)){}
 
    Montgomery &operator=(const Montgomery &b) = default;
    Montgomery operator-()const{return Montgomery()-Montgomery(*this);}
    Montgomery operator+(const Montgomery &b)const{return Montgomery(*this)+=b;}
    Montgomery operator-(const Montgomery &b)const{return Montgomery(*this)-=b;}
    Montgomery operator*(const Montgomery &b)const{return Montgomery(*this)*=b;}
    Montgomery operator/(const Montgomery &b)const{return Montgomery(*this)/=b;}
    Montgomery &operator+=(const Montgomery &b){
        v += b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery &operator-=(const Montgomery &b){
        v += mod-b.v;
        if(v >= mod) v -= mod;
        return (*this);
    }
    Montgomery &operator*=(const Montgomery &b){
        v = reduce(u128(v)*b.v);
        return (*this);
    }
    Montgomery &operator/=(const Montgomery &b){
        (*this) *= b.inv();
        return (*this);
    }
    Montgomery pow(long long b)const{
        Montgomery ret = 1,p = (*this);
        if(b < 0) p = p.inv(),b = -b;
        while(b){
            if(b&1) ret *= p;
            p *= p; b >>= 1;
        }
        return ret;
    }
    Montgomery inv()const{assert(v); return pow(mod-2);}
 
    friend bool operator!=(const Montgomery &a,const Montgomery &b){return a.v!=b.v;}
    friend bool operator==(const Montgomery &a,const Montgomery &b){return a.v==b.v;}
};
template<int idx> uint64_t Montgomery<idx>::mod; template<int idx> uint64_t Montgomery<idx>::N2; template<int idx> uint64_t Montgomery<idx>::Rsq;
using mont = Montgomery<0>;
 
bool MillerRabin(long long N,const vector<long long> &A){
    mont::setmod(N);
    long long s = __builtin_ctzll(N-1),d = N-1;
    d >>= s;
    for(auto &a : A){
        if(N <= a) break;
        mont x = mont(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 isprime(const long long N){
    if(N <= 1) return false;
    else if(N == 2) return true;
    else if(N%2 == 0) return false;
    else if(N < 4759123141LL) return MillerRabin(N,{2,7,61});
    else return MillerRabin(N, {2,325,9375,28178,450775,9780504,1795265022});
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    long long L,R; cin >> L >> R;
    int Need = 15010000;
    vector<bool> prime(Need+1,true);
    prime.at(0) = false; prime.at(1) = false;
    for(int i=2; i*i<=Need; i++){
        if(!prime.at(i)) continue;
        for(int k=i*i; k<=Need; k+=i) prime.at(k) = false;
    }

    for(long long a=3; a*a*a*a<=R; a++) if(prime.at(a)) for(long long b=a+1; a*a*b*b<=R; b++) if(prime.at(b)){
        for(long long c=max(b+1,(L+a*a*b-1)/(a*a*b)); a*a*b*c<=R; c++){
            if((c<=Need&&prime.at(c)) || isprime(c)){cout << a*a*b*c << endl; return 0;}
        
        }      

    }
    cout << "-1" << endl;
}