結果

問題 No.577 Prime Powerful Numbers
コンテスト
ユーザー tsongyuanmq
提出日時 2025-04-25 22:03:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 1,664 bytes
コンパイル時間 932 ms
コンパイル使用メモリ 78,008 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-04-25 22:03:31
合計ジャッジ時間 3,282 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 1 RE * 9
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:50:26: warning: ‘m’ may be used uninitialized [-Wmaybe-uninitialized]
   50 |             for(int p=1;p<=m;p++){
      |                         ~^~~
main.cpp:47:13: note: ‘m’ was declared here
   47 |         int m;
      |             ^

ソースコード

diff # 

#include<iostream>
#include<cmath>
#define int long long
#define maxn 210
#define maxm 1000010
using namespace std;
namespace IO{
    int read(){
        int x=0,f=1;char ch=getchar();
        while(ch<'0'||ch>'9'){
            if(ch=='-')f=-f;
            ch=getchar();
        }
        while(ch>='0'&&ch<='9'){
            x=x*10+ch-'0';
            ch=getchar(); 
        }return x*f;
    }
    void print(int x){
        if(x<0){
            x=-x;
            putchar('-');
        }
        if(x>9)print(x/10);
        putchar(x%10+'0');
    }
}using namespace IO;
int q,n,a,b[maxm];
bool vis[maxm];
int qpow(int a,int b){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a;
        b=b>>1;a=a*a;
    }return ans;
}
signed main(){
    q=read();
    for(int i=2;i<maxm;i++)vis[i]=1;
    for(int i=2;i*i<maxm+10;i++){
        if(!vis[i])continue;
        for(int j=i*2;j<maxm;j+=i)vis[j]=0;
    }
    for(int i=1;i<maxm;i++)if(vis[i])b[++a]=i;
    for(int i=1;i<=q;i++){
        n=read();
        int m;
        for(int j=1;j<maxm;j++)if(b[j]>n){m=j-1;break;}
        for(int j=1;j<=60;j++){
            for(int p=1;p<=m;p++){
                int x=qpow(b[p],j);
                if(x<0||x>n)continue;
                for(int k=1;k<=60;k++){
                    for(int c=1;c<=m;c++){
                        int y=qpow(b[c],k);
                        if(y<0||y>n)continue;
                        if(x+y==n){
                            cout<<"Yes\n";
                            goto yu;
                        }
                    }
                }       
            } 
             
        }cout<<"No\n";
        yu:continue;
    }
    return 0;
}
0