結果
問題 |
No.577 Prime Powerful Numbers
|
ユーザー |
|
提出日時 | 2025-04-27 21:06:40 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,294 bytes |
コンパイル時間 | 2,177 ms |
コンパイル使用メモリ | 192,356 KB |
実行使用メモリ | 34,920 KB |
最終ジャッジ日時 | 2025-04-27 21:06:49 |
合計ジャッジ時間 | 8,950 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | -- * 1 |
other | TLE * 1 -- * 9 |
ソースコード
#include<bits/stdc++.h> #define int long long using namespace std; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<48||ch>57) { if(ch==45)f=-1; ch=getchar(); } while(ch>=48&&ch<=57) { x=(x<<1)+(x<<3)+(ch&15); ch=getchar(); } return x*f; } inline void write(int x) { if(x<0)x=-x,putchar(45); if(x>9)write(x/10); putchar(x%10+48); return; } const int M=1e7; int K,prime[M+10]; bool notPrime[M+10]; inline void init() { notPrime[0]=notPrime[1]=1; for(int i=2;i<=M;++i) { if(!notPrime[i])prime[++K]=i; for(int j=1;j<=K&&i*prime[j]<=M;++j) { notPrime[prime[j]*i]=1; if(i%prime[j]==0)break; } } return; } signed main() { //freopen("number.in","r",stdin); //freopen("number.out","w",stdout); int T=read(); init(); for(int czs=1;czs<=T;++czs) { int n=read(); if(n%2==0) { puts(n==2?"No":"Yes"); continue; } bool fg=0,timeout=0; for(int i=1;i<=K;++i) { for(int j=prime[i];j<=n;j*=prime[i]) { int m=n-j; for(int k=i;k<=K;++k) { for(int l=prime[k];l<=m;l*=prime[k]) { if(l==m) { fg=1; //cerr<<j<<" "<<l<<"\n"; break; } } if(fg||timeout)break; } if(fg||timeout)break; } if(fg||timeout)break; } puts(fg?"Yes":"No"); } return 0; }