No.2379 Burnside's Theorem
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 210
作問者 :
箱星
/ テスター :
👑 
p-adic
タグ : / 解いたユーザー数 210
作問者 :
箱星
/ テスター :
👑 p-adic
問題文最終更新日: 2023-05-19 20:17:02
問題文
バーンサイドの定理によると、素数 $p,q$ および負でない整数 $a,b$ に対して、位数が $p^aq^b$ の群は可解です。
正の整数 $N$ が与えられるので、素数 $p,q$ および負でない整数 $a,b$ を用いて $N=p^aq^b$ と表せるか判定してください。
制約
$N$ は $1\le N\le 10^{12}$ をみたす整数入力
$N$
出力
$N=p^aq^b$ と表せるなら Yes、表せないなら No と出力してください。
サンプル
サンプル1
入力
45
出力
Yes
$45=3^2\times 5^1$ と表せます。
サンプル2
入力
1024
出力
Yes
$1024=2^{10}\times 3^0$ と表せます。
サンプル3
入力
168
出力
No
サンプル4
入力
123456789000
出力
No
入力が 32bit 整数に収まらない場合に注意してください。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。