結果

問題 No.577 Prime Powerful Numbers
ユーザー chocoruskchocorusk
提出日時 2018-08-04 06:46:09
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 249 ms / 2,000 ms
コード長 3,011 bytes
コンパイル時間 1,647 ms
コンパイル使用メモリ 92,404 KB
実行使用メモリ 5,200 KB
最終ジャッジ日時 2023-10-19 21:45:22
合計ジャッジ時間 2,203 ms
ジャッジサーバーID
（参考情報） 		judge11 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
5,200 KB
testcase_01 AC 20 ms
5,200 KB
testcase_02 AC 10 ms
5,200 KB
testcase_03 AC 71 ms
5,200 KB
testcase_04 AC 19 ms
5,200 KB
testcase_05 AC 195 ms
5,200 KB
testcase_06 AC 78 ms
5,200 KB
testcase_07 AC 249 ms
5,200 KB
testcase_08 AC 65 ms
5,200 KB
testcase_09 AC 55 ms
5,200 KB
testcase_10 AC 10 ms
5,200 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <random>

using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

vector<ll> prime;
bool isprime[1000000];

void sieve(){
	for(ll i=0; i<1000000; i++){
		isprime[i]=1;
	}
	isprime[0]=0, isprime[1]=0;
	for(ll i=2; i<1000000; i++){
		if(isprime[i]){
			prime.push_back(i);
			for(ll j=2*i; j<1000000; j+=i){
				isprime[j]=0;
			}
		}
	}
	return;
}

ll mulmod(ll a, ll b, ll m){
	ll x=1000000000;
  if(m<x) return a*b%m;
	ll m1=m/x, m2=m%x, a1=a/x, a2=a%x, b1=b/x, b2=b%x;
	ll q1=a1*b1/m1, r1=a1*b1%m1;
	ll c=r1*x+a1*b2+a2*b1-q1*m2, d=a2*b2;
	ll q2, r2;
	if(c<0) q2=-(-c+m1)/m1;
	else q2=c/m1;
	r2=c-q2*m1;
	ll ans=r2*x+d-q2*m2;
	if(ans<0) ans=(m-(-ans%m))%m;
	else ans%=m;
	return ans;
}

long long int powmod(long long int a, long long int k, long long int m){
    if(a==0) return 0;
    long long int ap=a, ans=1;
    while(k>0){
        if(k%2==1){
            ans=mulmod(ans, ap, m);
        }
        ap=mulmod(ap, ap, m);
        k/=2;
    }
    return ans;
}

bool is_prime(ll n){
	if(n==2){
		return true;
	}
	if(n==1 || n%2==0){
		return false;
	}
	ll d=n-1;
	int k=0;
	while(d%2==0){
		d/=2;
		k++;
	}
	random_device rnd;
	mt19937_64 mt(rnd());
	uniform_int_distribution<ll> rndn(2, n-1);
	for(int i=0; i<50; i++){
		ll a=rndn(mt);
		bool comp=1;
		ll ap=powmod(a, d, n);
		if(ap==1 || ap==n-1) continue;
		for(int r=1; r<k; r++){
			ap=mulmod(ap, ap, n);
			if(ap==n-1){
				comp=0;
				break;
			}
		}
		if(comp) return false;
	}
	return true;
}

ll root(ll n, int k){
	ll m1=0, m2;
	if(k==2){
		m2=1e9;
	}else if(k==3){
		m2=1e6;
	}else if(k==4){
		m2=32000;
	}else{
		m2=4000;
	}
	while(m1!=m2){
		ll m=(m1+m2+1)/2;
		ll mp=1;
		for(int i=0; i<k; i++) mp*=m;
		if(mp<=n){
			m1=m;
		}else{
			m2=m-1;
		}
	}
	ll mp=1;
	for(int i=0; i<k; i++) mp*=m1;
	if(mp==n){
		return m1;
	}else{
		return -1;
	}
}

int main()
{
	int q;
	cin>>q;
	sieve();
	for(int i=0; i<q; i++){
		ll n;
		cin>>n;
		if(n<=3){
			cout<<"No"<<endl;
			continue;
		}
		if(n%2==0){
			cout<<"Yes"<<endl;
			continue;
		}
		ll p2=2;
		bool yes=0;
		while(p2<n){
			ll n1=n-p2;
			if(n1<1000000){
				if(isprime[n1]){
					cout<<"Yes"<<endl;
					yes=1;
					break;
				}
			}else{
				if(is_prime(n1)){
					cout<<"Yes"<<endl;
					yes=1;
					break;
				}
			}
			for(int k=2; k<=5; k++){
				ll r=root(n1, k);
				if(r==-1) continue;
				if(r<1000000){
					if(isprime[r]){
						cout<<"Yes"<<endl;
						yes=1;
						break;
					}
				}else{
					if(is_prime(r)){
						cout<<"Yes"<<endl;
						yes=1;
						break;
					}
				}
			}
			if(yes) break;
			for(int i=1; prime[i]<=1000; i++){
				ll x=n1;
				while(x%prime[i]==0) x/=prime[i];
				if(x==1){
					cout<<"Yes"<<endl;
					yes=1;
					break;
				}
			}
			if(yes) break;
			p2*=2;
		}
		if(!yes) cout<<"No"<<endl;
	}
	return 0;
}
0