結果

問題 No.577 Prime Powerful Numbers
ユーザー dontwannacry
提出日時 2025-04-25 21:52:52
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,427 bytes
コンパイル時間 2,318 ms
コンパイル使用メモリ 194,848 KB
実行使用メモリ 55,180 KB
最終ジャッジ日時 2025-04-25 21:53:27
合計ジャッジ時間 8,349 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 1
other TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf = 0x3f3f3f3f;
ll N;
int prime[10000010],len;
bitset<100000010>vis;
void init(){
	vis[0] = vis[1] = 1;
	for(int i = 2;i <= 100000000;++i){
		if(!vis[i]){prime[++len] = i;}
		for(int j = 1;j <= len&&prime[j]*i <= 100000000;++j){
			vis[prime[j]*i] = 1;
			if(i%prime[j] == 0){break;}
		}
	}
	for(int i = 10000;i >= 2;--i){
		if(vis[i]){continue;}
		for(ll j = i*i;j <= 100000000;j *= i){vis[j] = 0;}
	}
}
bool isprime(ll x){
	for(int i = 1;i <= len&&1ll*prime[i]*prime[i] <= x;++i){
		if(x%vis[i] == 0){return 0;}
	}
	return 1;
}
bool check(ll x){
	if(x <= 100000000){return (!vis[x]);}
	for(int i = 1;i <= len;++i){
		if(x%vis[i] == 0){
			while(x > 1&&x%vis[i] == 0){x /= vis[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(){
	cin >> N;
	if(N <= 100000000){
		for(int i = N/2;i >= 2;--i){if(!vis[i]&&!vis[N-i]){cout << "Yes\n";return;}}
		cout << "No\n";return;
	}
	if(N&1){
		for(ll j = 2;j < N;j <<= 1){if(check(N-j)){cout << "Yes\n";return;}}
		cout << "No\n";return;
	}
	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