結果

問題 No.2751 429-like Number
コンテスト
ユーザー GOTKAKO
提出日時 2024-05-10 21:37:59
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 76 ms / 4,000 ms
コード長 3,812 bytes
コンパイル時間 2,027 ms
コンパイル使用メモリ 201,920 KB
最終ジャッジ日時 2025-02-21 12:25:37
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 6
other AC * 22
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct Modint64{
    //2^62未満&奇数modのみ.
    using Mint = Modint64;
    using u64 = uint64_t;
    using u128 = __uint128_t;
    static u64 mod,mod2,invmod,t128;
    u64 v = 0;
 
    Modint64(){v = 0;} Modint64(long long w){v = reduce((u128(w)+mod)*t128);}
    u64 val()const{
        u64 ret = reduce(v);
        return ret >= mod ? ret-mod : ret;
    }
    static u64 getmod(){return mod;}
    static u64 getinvmod(){
        u64 ret = mod;
        for(int i=0; i<5; i++) ret *= 2-mod*ret;
        return ret;
    }
    static void setmod(u64 m){
        assert((m<(1LL<<62)) && (m&1));
        mod = m; mod2 = m*2;
        t128 = -u128(mod)%mod;
        invmod = getinvmod();
    }
    static u64 reduce(const u128 &v){return (v+u128(u64(v)*u64(-invmod))*mod) >> 64;}
 
    Mint operator+(const Mint &b)const{return Mint(*this)+=b;}
    Mint operator-(const Mint &b)const{return Mint(*this)-=b;}
    Mint operator*(const Mint &b)const{return Mint(*this)*=b;}
    Mint operator/(const Mint &b)const{return Mint(*this)/=b;}
    Mint operator-()const{return Mint()-Mint(*this);}
    Mint& operator+=(const Mint &b){
        v += b.v;
        if(v >= mod2) v -= mod2;
        return *this; 
    }
    Mint& operator-=(const Mint &b){
        v += mod2-b.v;
        if(v >= mod2) v -= mod2;
        return *this;
    }
    Mint& operator*=(const Mint &b){
        v = reduce(u128(v)*b.v);
        return *this;
    }
    Mint& operator/=(const Mint &b){
        *this *= b.inv();
        return *this;
    }
    Mint pow(u128 b)const{
        Mint ret(1),p(*this);
        while(b){
            if(b&1) ret *= p;
            p = p*p; b >>= 1;
        }
        return ret;
    }
    Mint inv()const{return pow(mod-2);}
    
    bool operator==(const Mint &b)const{return (v >= mod?v-mod:v) == (b.v >= mod?b.v-mod:b.v);}
    bool operator!=(const Mint &b)const{return (v >= mod?v-mod:v) != (b.v >= mod?b.v-mod:b.v);}
};
typename Modint64::u64
Modint64::mod,Modint64::mod2,Modint64::invmod,Modint64::t128;
 
bool MillerRabin(long long N,vector<long long> A){
    using Mint = Modint64;
    Mint::setmod(N);
    int s = 0; long long d = N-1;
    while(d%2 == 0){s++,d >>= 1;}
    for(auto a : A){
        if(N <= a) return true;
        int t = 0; Mint x = Mint(a).pow(d);
        if(x != 1){
            for(; t < s; t++){
                if(x == N-1) break;
                x *= x;
            }
            if(t == s) return false;
        }
    }
    return true;
}
bool isprime(long long N){
    if(N <= 1) return false;
    if(N == 2) return true;
    if(N%2 == 0) return false;
    if(N < 475912314) return MillerRabin(N,{2,7,61});
    return MillerRabin(N,{2,325,9375,28178,450775,9780504,1795265022});
}

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

    int Q; cin >> Q;
    int Need = 1000000;
    vector<int> allp;
    vector<bool> prime(Need+1,true);
    prime.at(0) = false; prime.at(1) = false;
    for(int i=2; i<=Need; i++){
        if(!prime.at(i)) continue;
        allp.push_back(i);
        for(long long k=((long long)i)*i; k<=Need; k+=i) prime.at(k) = false;
    }
    
    int n = allp.size();
    while(Q--){
        long long x; cin >> x;
        
        bool ok = false;
        for(int i=0; i<n; i++){
            long long a = allp.at(i);
            if(a*a*a > x) break;
            if(x%a) continue;
            for(int k=i; k<n; k++){
                long long b = allp.at(k);
                if(a*b*b > x) break;
                if(x%(a*b)) continue;
                long long c = x/a/b;
                if(b <= c && isprime(c)){ok = true; break;}
                else break;
            }
            break;
        }
        if(ok) cout << "Yes" << "\n";
        else cout << "No" << "\n";
    }
}
0