結果

問題 No.577 Prime Powerful Numbers
ユーザー CZS_AK_IOI2025
提出日時 2025-04-25 22:44:17
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,472 bytes
コンパイル時間 2,370 ms
コンパイル使用メモリ 195,764 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-25 22:44:20
合計ジャッジ時間 2,952 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 WA * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp:15:25: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   15 |         li ll pow(re ll a,re ll b,re ll p)
      |                         ^
main.cpp:15:33: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   15 |         li ll pow(re ll a,re ll b,re ll p)
      |                                 ^
main.cpp:15:41: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   15 |         li ll pow(re ll a,re ll b,re ll p)
      |                                         ^
main.cpp: In function ‘long long int Miller_Rabin::pow(long long int, long long int, long long int)’:
main.cpp:17:23: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   17 |                 re ll ans=1;
      |                       ^~~
main.cpp: At global scope:
main.cpp:21:29: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   21 |         li bool check(re ll x,re ll p)
      |                             ^
main.cpp:21:37: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   21 |         li bool check(re ll x,re ll p)
      |                                     ^
main.cpp: In function ‘bool Miller_Rabin::check(long long int, long long int)’:
main.cpp:24:23: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   24 |                 re ll t,k=x-1;
      |                       ^
main.cpp:24:25: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   24 |                 re ll t,k=x-1;
      |                         ^
main.cpp: At global scope:
main.cpp:32:30: warning: ISO C++17 does not allow ‘register’ storage class specifier [-Wregister]
   32 |         inline bool MR(re ll x)
      |                              ^
main.cpp: In function ‘bool Miller_Rabin::MR(long long int)’:
main.cpp:35:28: warni

ソースコード

diff # 

#include<bits/stdc++.h>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define int long long
#define li inline
#define re register
#define ll long long
#define abs(a) ((a)>0?(a):-(a))
using namespace std;
namespace Miller_Rabin
{
	const int Pcnt=12;
	const ll p[Pcnt]={2,3,5,7,11,13,17,19,61,2333,4567,24251};
	li ll pow(re ll a,re ll b,re ll p)
	{
		re ll ans=1;
		for(;b;a=a*a%p,b>>=1)if(b&1)ans=ans*a%p;
		return ans;
	}
	li bool check(re ll x,re ll p)
	{
		if(x%p==0||pow(p%x,x-1,x)^1)return true;
		re ll t,k=x-1;
		while((k^1)&1)
		{
			t=pow(p%x,k>>=1,x);
			if(t^1&&t^x-1)return true;
			if(!(t^x-1))return false;
		}return false;
	}
	inline bool MR(re ll x)
	{
		if(x<2)return false;
		for(re int i=0;i^Pcnt;++i)
		{
			if(!(x^p[i]))return true;
			if(check(x,p[i]))return false;
		}return true;
	}
}
namespace Pollard_Rho
{
#define Rand(x) (1ll*rand()*rand()%(x)+1)
	li ll gcd(const ll a,const ll b){return b?gcd(b,a%b):a;}
	li ll mul(const re ll x,const re ll y,const re ll X)
	{
		ll k=(1.0L*x*y)/(1.0L*X)-1,t=x*y-k*X;
		while(t<0)t+=X;return t;
	}
	li ll PR(const re ll x,const re ll y)
	{
		re int t=0,k=1;re ll v0=Rand(x-1),v=v0,d,s=1;
		while(true)
		{
			v=(mul(v,v,x)+y)%x,s=mul(s,abs(v-v0),x);
			if(!(v^v0)||!s)return x;
			if(++t==k){if((d=gcd(s,x))^1)return d;v0=v,k<<=1;}
		}
	}
	li void Resolve(re ll x,re ll&ans)
	{
		if(!(x^1)||x<=ans)return;
		if(Miller_Rabin::MR(x)){if(ans<x)ans=x;return;}
		re ll y=x;while((y=PR(x,Rand(x)))==x);while(!(x%y))x/=y;
		Resolve(x,ans);Resolve(y,ans);
	}
	li long long check(ll x)
	{
		re ll ans=0;Resolve(x,ans);
		return ans;
	}
}
inline bool isprime(long long x){return Pollard_Rho::check(x)==x;}
inline long long ksm(long long d,long long z){
	long long res=1;
	while(z){
		if(z&1)res*=d;
		d*=d;z>>=1;
	}
	return res;
}
inline long long CZS(long long x,long long z){
	long long L=0,R=1e18,mid,AAns=-1;
	while(L<=R){
		mid=(L+R)>>1;
		if(ksm(mid,z)>=x)AAns=mid,R=mid-1;
		else L=mid+1;
	}
	return AAns;
}
inline long long chk(long long x){
	long long i=2,rep=0;
	while(1){
		long long res=pow(x,1.00/i);++i;
		if(ksm(res,i-1)==x&&isprime(res))return 1;
		if(res==rep)break;
		rep=res;
	}
	return 0;
}
inline bool liliang(long long x){
	for(long long i=2,j=0;i<=x;i*=2,++j){
		if(chk(x-i))return 1;
	}
	if(x&1){
		return 0;
	}
	else return liliang(x/2);
}
signed main()
{
	srand(time(0));
	int Q;cin>>Q;
	while(Q--){
		long long n;cin>>n;
		if(liliang(n))cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}
0