問題一覧 > 通常問題

No.577 Prime Powerful Numbers

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 40
作問者 : square1001 / テスター : WA_TLE
2 ProblemId : 1807 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2017-10-13 18:05:33

問題文

square1001は、素数の k 乗 (k は正の整数) で表されるような数を「重要で力のある数」と定義することにしました。

正の整数 N が与えられます。N=pa+qb となるような素数 p,q と正の整数 a,b の組み合わせが存在するか判定しなさい。
すなわち、N2 つの「重要で力のある数」の和で表すことができるか判定しなさい。

ただし、テストケースが Q 個あるので、i 番目のテストケースの数を Ni とします。

入力

Q
N1
N2
 :
NQ

1 行目には、整数 Q (1Q200) が一行に与えられます。
i+1 行目には、整数 Ni (1Ni1018) が一行に与えられます。

出力

i 行目には、Ni=pa+qb となるような (p,q,a,b) の組み合わせが存在するならばYes, そうでないならばNoと出力しなさい。

サンプル

サンプル1
入力
2
251
149
出力
Yes
No

251=23+35 と表せるので、(p,q,a,b)=(2,3,3,5) が条件を満たします。
149 は、2つの「重要で力のある数」の和で表すことができません。

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。