No.2993 冪乗乗 mod 冪乗
タグ : / 解いたユーザー数 2
作問者 : 👑

問題文
この問題の実行時間制限は10000[ms]です。writer解の実行時間はc++で415[ms]、PyPy3で5293[ms]、Python3で TLE となっており、高速な言語・処理系の使用を推奨します。
問題文
以下のような問題を考えます:
入力に 以上の整数 と つの非負整数 が与えられます。
以下の 条件を全て満たす整数 が存在するか否かを判定し、存在する場合はそのような を1つ求めてください:
- である。
- 次の条件を満たす非負整数 が存在する:
- 以上の任意の非負整数 に対し である。
以下、上記 条件をこの問題に対する解条件と呼びます。
入力の最初に正整数 が与えられます。 個の問題に答えてください。
入力
以下の各正整数 に対し、 個目の問題に対する入力 を と置きます。
この時、入力は次の形式で標準入力から 行で与えられます:
- 行目に が与えられます。
- 以下の各正整数 に対し、 行目に 個目の問題に対する入力 が半角空白区切りで与えられます。
制約
入力は以下の制約を満たします:
- は を満たす整数
- 以下の任意の正整数 に対し、
- は を満たす整数
- は かつ を満たす整数
- は を満たす整数
出力
以下の各正整数 に対し、 番目の問題に対する解条件を満たす整数 が存在する場合はそのような を 行目に出力し、存在しない場合は -1
と 行目に出力してください。
最後に改行してください。
なおこの問題はスペシャルジャッジ問題です。正解が複数ある場合はどれを出力しても構いません。
ただし出力は上述した形式に厳格に従ってください。例えば余計な空白がある場合のジャッジの挙動は保証されません。
サンプル
サンプル1
入力
1 2 0 0
出力
-1
整数 がテストケース に対する解条件を満たすということは、以下の 条件を満たすということです:
- である。
- 次の条件を満たす非負整数 が存在する:
- 以上の任意の非負整数 に対し である。
条件1から は に限られますが、 とすると非負整数 をどのように選んでも が の時に成り立ちませんので条件2が成り立たず、従って解条件を満たす整数 は存在しません。
サンプル2
入力
1 2 0 1
出力
0
整数 がテストケース に対する解条件を満たすということは、以下の 条件を満たすということです:
- である。
- 次の条件を満たす非負整数 が存在する:
- 以上の任意の非負整数 に対し である。
と定めると は条件1を満たしますし、 と定めれば 以上の任意の非負整数 に対し も成り立つので条件2も満たします。従って は解条件を満たします。
サンプル3
入力
1 2 1 1
出力
0
整数 がテストケース に対する解条件を満たすということは、以下の 条件を満たすということです:
- である。
- 次の条件を満たす非負整数 が存在する:
- 以上の任意の非負整数 に対し である。
と定めると は条件1を満たしますし、 と定めれば 以上の任意の非負整数 に対し も成り立つので条件2も満たします。従って は解条件を満たします。
サンプル4
入力
6 3 0 0 3 0 1 3 0 2 3 1 0 3 1 1 3 1 2
出力
-1 0 -1 -1 0 -1
個の問題に答えてください。
サンプル5
入力
18 4 0 0 4 0 1 4 0 2 4 0 3 4 0 4 4 0 5 4 1 0 4 1 1 4 1 2 4 1 3 4 1 4 4 1 5 4 2 0 4 2 1 4 2 2 4 2 3 4 2 4 4 2 5
出力
-1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 0 -1 4 -1 12
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。