No.577 Prime Powerful Numbers

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 25
作問者 : square1001square1001 / テスター : WA_TLEWA_TLE
0 ProblemId : 1807 / 出題時の順位表

問題文

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

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

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

入力

$Q$
$N_1$
$N_2$
 :
$N_Q$

$1$ 行目には、整数 $Q \ (1 \le Q \le 200)$ が一行に与えられます。
$i+1$ 行目には、整数 $N_i \ (1 \le N_i \le 10^{18})$ が一行に与えられます。

出力

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

サンプル

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

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

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。