No.2189 六平方和
タグ : / 解いたユーザー数 23
作問者 : 👑
p-adic
/ テスター :
👑 
testestest
問題文
入力に正整数 $N$ と $M$ と $B$ が与えられます。
$\displaystyle x_0^2 + x_1^2 + x_2^2 + x_3^2 + x_4^2 + x_5^2 \equiv M^N \pmod{B} $
を満たす $10^9$ 以下の正整数の組み合わせ $(x_0,x_1,x_2,x_3,x_4,x_5)$ が存在するか否かを判定し、存在する場合はそのような $(x_0,x_1,x_2,x_3,x_4,x_5)$ を $1$ 組求めてください。
入力
入力は次の形式で標準入力から与えられます：
$N$ $M$ $B$
$1$ 行に $N, M, B$ が半角空白区切りで与えられます。
制約
入力は以下の制約を満たします：
- $N$ は $10^{18}$ 以下の正整数
- $M$ は $10^3$ 以下の正整数
- $B$ は $10^9$ 以下の正整数
出力
$\displaystyle x_0^2 + x_1^2 + x_2^2 + x_3^2 + x_4^2 + x_5^2 \equiv M^N \pmod{B} $
を満たす $10^9$ 以下の正整数の組み合わせ $(x_0,x_1,x_2,x_3,x_4,x_5)$ が存在しない場合はNOと出力してください。
存在する場合は $1$ 行目にYESと出力し、$2$ 行目にそのような $x_0,x_1,x_2,x_3,x_4,x_5$ を半角空白区切りで出力してください。
ただしこの問題はスペシャルジャッジ問題です。正解は $1$ 通りではないかもしれませんが、$1$ 通りだけ出力してください。
最後に改行してください。
サンプル
サンプル1
入力
1 2 2
出力
YES 1 1 1 1 1 1
$(x_0,x_1,x_2,x_3,x_4,x_5) = (1,1,1,1,1,1)$ の各成分は $10^9$ 以下の正整数であり、その平方和 $1^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 6$ と $M^N = 2^1 = 2$ は法 $2$ で合同です。
サンプル2
入力
2 3 4
出力
YES 2 1 1 1 1 1
$(x_0,x_1,x_2,x_3,x_4,x_5) = (2,1,1,1,1,1)$ の各成分は $10^9$ 以下の正整数であり、その平方和 $2^2 + 1^2 + 1^2 + 1^2 + 1^2 + 1^2 = 9$ と $M^N = 3^2 = 9$ は等しいので特に法 $4$ で合同です。
サンプル3
入力
3 4 11
出力
YES 2 1 2 1 1 3
$(x_0,x_1,x_2,x_3,x_4,x_5) = (2,1,2,1,1,3)$ の各成分は $10^9$ 以下の正整数であり、その平方和 $2^2 + 1^2 + 2^2 + 1^2 + 1^2 + 3^2 = 20$ と $M^N = 4^3 = 64$ は法 $11$ で合同です。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。