問題一覧 > 教育的問題

No.2993 冪乗乗 mod 冪乗

レベル : / 実行時間制限 : 1ケース 10.000秒 / メモリ制限 : 512 MB / スペシャルジャッジ問題 （複数の解が存在する可能性があります）
タグ : / 解いたユーザー数 4
作問者 : 👑 p-adicp-adic / テスター : 👑 testestesttestestest
0 ProblemId : 9132 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-12-12 07:51:09

問題文

この問題の実行時間制限は10000[ms]です。writer解の実行時間はc++で415[ms]、PyPy3で5293[ms]、Python3で TLE となっており、高速な言語・処理系の使用を推奨します。

問題文

以下のような問題を考えます：

入力に $2$ 以上の整数 $B$ と $2$ つの非負整数 $N,M$ が与えられます。

以下の $2$ 条件を全て満たす整数 $a$ が存在するか否かを判定し、存在する場合はそのような $a$ を１つ求めてください：

  1. $0 \leq a < B^N$ である。
  2. 次の条件を満たす非負整数 $n_0$ が存在する：
    • $n_0$ 以上の任意の非負整数 $n$ に対し $M^{B^n} \equiv 1 + B^n a \pmod{B^{n+N}}$ である。

以下、上記 $2$ 条件をこの問題に対する解条件と呼びます。

入力の最初に正整数 $T$ が与えられます。$T$ 個の問題に答えてください。

入力

$T$ 以下の各正整数 $t$ に対し、$t$ 個目の問題に対する入力 $B,N,M$ を $B_t,N_t,M_t$ と置きます。

この時、入力は次の形式で標準入力から $1 + T$ 行で与えられます：

  • $1$ 行目に $T$ が与えられます。
  • $T$ 以下の各正整数 $t$ に対し、$1 + t$ 行目に $t$ 個目の問題に対する入力 $B_t, N_t, M_t$ が半角空白区切りで与えられます。
$T$
$B_1$ $N_1$ $M_1$
$\vdots$
$B_T$ $N_T$ $M_T$

制約

入力は以下の制約を満たします：

  • $T$ は $1 \leq T \leq 10^5$ を満たす整数
  • $T$ 以下の任意の正整数 $t$ に対し、
    • $B_t$ は $2 \leq B_t \leq 10^6$ を満たす整数
    • $N_t$ は $0 \leq N_t$ かつ $B_t^{N_t} \leq 10^6$ を満たす整数
    • $M_t$ は $0 \leq M_t \leq 10^{18}$ を満たす整数

出力

$T$ 以下の各正整数 $t$ に対し、$t$ 番目の問題に対する解条件を満たす整数 $a$ が存在する場合はそのような $a$ を $t$ 行目に出力し、存在しない場合は -1 と $t$ 行目に出力してください。

最後に改行してください。

　

なおこの問題はスペシャルジャッジ問題です。正解が複数ある場合はどれを出力しても構いません。

ただし出力は上述した形式に厳格に従ってください。例えば余計な空白がある場合のジャッジの挙動は保証されません。

サンプル

サンプル1
入力
1
2 0 0
出力
-1

整数 $a$ がテストケース $(B,N,M) = (2,0,0)$ に対する解条件を満たすということは、以下の $2$ 条件を満たすということです：

  1. $0 \leq a < 1$ である。
  2. 次の条件を満たす非負整数 $n_0$ が存在する：
    • $n_0$ 以上の任意の非負整数 $n$ に対し $0 \equiv 1 + 2^n a \pmod{2^n}$ である。

条件1から $a$ は $0$ に限られますが、$a = 0$ とすると非負整数 $n_0$ をどのように選んでも $0 \equiv 1 + 2^n a \pmod{2^n}$ が $n = \max \{n_0,1\}$ の時に成り立ちませんので条件2が成り立たず、従って解条件を満たす整数 $a$ は存在しません。

サンプル2
入力
1
2 0 1
出力
0

整数 $a$ がテストケース $(B,N,M) = (2,0,1)$ に対する解条件を満たすということは、以下の $2$ 条件を満たすということです：

  1. $0 \leq a < 1$ である。
  2. 次の条件を満たす非負整数 $n_0$ が存在する：
    • $n_0$ 以上の任意の非負整数 $n$ に対し $1 \equiv 1 + 2^n a \pmod{2^n}$ である。

$a = 0$ と定めると $a$ は条件1を満たしますし、$n_0 = 0$ と定めれば $n_0$ 以上の任意の非負整数 $n$ に対し $1 \equiv 1 + 2^n a \pmod{2^n}$ も成り立つので条件2も満たします。従って $a$ は解条件を満たします。

サンプル3
入力
1
2 1 1
出力
0

整数 $a$ がテストケース $(B,N,M) = (2,1,1)$ に対する解条件を満たすということは、以下の $2$ 条件を満たすということです：

  1. $0 \leq a < 2$ である。
  2. 次の条件を満たす非負整数 $n_0$ が存在する：
    • $n_0$ 以上の任意の非負整数 $n$ に対し $1 \equiv 1 + 2^n a \pmod{2^{n+1}}$ である。

$a = 0$ と定めると $a$ は条件1を満たしますし、$n_0 = 0$ と定めれば $n_0$ 以上の任意の非負整数 $n$ に対し $1 \equiv 1 + 2^n a \pmod{2^{n+1}}$ も成り立つので条件2も満たします。従って $a$ は解条件を満たします。

サンプル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

$T = 6$ 個の問題に答えてください。

サンプル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もしくは右上の雲マークをクリックしてアカウントを作成してください。