結果

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

ソースコード

diff # 

#include<bits/stdc++.h>
#include<cstdlib>
#include<cstdio>
#include<ctime>
#define li inline
#define re register
#define ll __int128
#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(int x){return Pollard_Rho::check(x)==x;}
inline int ksm(int d,int z){
	int res=1;
	while(z){
		if(z&1)res*=d;
		d*=d;z>>=1;
	}
	return res;
}
inline int chk(int x){
	int i=2,rep=0;
	while(1){
		int 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(int x){
	if(x&1){
		for(int i=1,j=0;i<=x&&j<=63;i*=2,++j){
			if(chk(x-i))return 1;
		}
		return 0;
	}
	else return 1;
}
signed main()
{
	srand(127721127);
	int Q;cin>>Q;
	while(Q--){
		int n;cin>>n;
		if(liliang(n))cout<<"Yes\n";
		else cout<<"No\n";
	}
	return 0;
}
0