結果

問題 No.577 Prime Powerful Numbers
ユーザー dontwannacry
提出日時 2025-05-02 10:39:39
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,175 bytes
コンパイル時間 2,098 ms
コンパイル使用メモリ 195,296 KB
実行使用メモリ 7,840 KB
最終ジャッジ日時 2025-05-02 10:39:49
合計ジャッジ時間 8,204 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 9 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int prime[1000010],len;
bitset<10000010>vis;
inline void modadd(ll &a,ll b,const ll MOD){a += b;if(a >= MOD){a -= MOD;}}
ll qmul(ll A,ll B,const ll MOD){
    ll res = 0;
    while(B){
        if(B&1){modadd(res,A,MOD);}
        modadd(A,A,MOD);
        B >>= 1;
    }
    return res;
}
ll qpow(ll A,ll B,const ll MOD){
    ll res = 1;
    while(B){
        if(B&1){res = qmul(res,A,MOD);}
        A = qmul(A,A,MOD);
        B >>= 1;
    }
    return res;
}
void init(){
	vis[0] = vis[1] = 1;
	for(int i = 2;i <= 10000000;++i){
		if(!vis[i]){prime[++len] = i;}
		for(int j = 1;j <= len&&prime[j]*i <= 10000000;++j){
			vis[prime[j]*i] = 1;
			if(i%prime[j] == 0){break;}
		}
	}
	for(int i = 3500;i >= 2;--i){
		if(vis[i]){continue;}
		for(ll j = i*i;j <= 10000000;j *= i){vis[j] = 0;}
	}
}
bool Miller_Rabin(const ll x,const ll base){
    ll u = x-1;
    while(!(u&1)){u >>= 1;}
    ll v = qpow(base,u,x);
    if(v == 1){return 1;}
    while(u < x-1){
        if(v == x-1){return 1;}
        v = qmul(v,v,x);
        u <<= 1;
    }
    return 0;
}
bool isprime(ll x){
    if(x <= 1){return 0;}
    ll checkbase[8] = {2,3,5,7,11,13,17,37};
    for(int i = 0;i < 8;++i){
        if(x == checkbase[i]){return 1;}
        if(x%checkbase[i] == 0){return 0;}
        if(!Miller_Rabin(x,checkbase[i])){return 0;}
    }
	return 1;
}
bool check(ll x){
	if(x <= 10000000){return (!vis[x]);}
	if(isprime(x)){return 1;}
	for(int i = 1;i <= len;++i){
		if(x%prime[i] == 0){
			while(x > 1&&x%prime[i] == 0){x /= prime[i];}
			return x == 1;
		}
	}
	ll tmp = sqrt(x);
	if(tmp*tmp == x&&isprime(tmp)){return 1;}
	if((tmp+1)*(tmp+1) == x&&isprime((tmp+1))){return 1;}
	return 0;
}
void solve(){
	ll N;cin >> N;
	if(N&1){
		for(ll j = 2;j < N;j <<= 1){if(check(N-j)){cout << "Yes\n";return;}}
		cout << "No\n";return;
	}
	if(N == 2){cout << "No\n";}
	cout << "Yes\n";return;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    // freopen("number.in","r",stdin);
    // freopen("number.out","w",stdout);
    int T = 1;cin >> T;init();
	for(int i = 1;i <= T;++i){solve();}
	return 0;
}
0