問題一覧 > 教育的問題

No.2993 冪乗乗 mod 冪乗

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

問題文

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

問題文

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

入力に 22 以上の整数 BB22 つの非負整数 N,MN,M が与えられます。

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

  1. 0a<BN0 \leq a < B^N である。
  2. 次の条件を満たす非負整数 n0n_0 が存在する:
    • n0n_0 以上の任意の非負整数 nn に対し MBn1+Bna(modBn+N)M^{B^n} \equiv 1 + B^n a \pmod{B^{n+N}} である。

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

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

入力

TT 以下の各正整数 tt に対し、tt 個目の問題に対する入力 B,N,MB,N,MBt,Nt,MtB_t,N_t,M_t と置きます。

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

  • 11 行目に TT が与えられます。
  • TT 以下の各正整数 tt に対し、1+t1 + t 行目に tt 個目の問題に対する入力 Bt,Nt,MtB_t, N_t, M_t が半角空白区切りで与えられます。
TT
B1B_1 N1N_1 M1M_1
\vdots
BTB_T NTN_T MTM_T

制約

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

  • TT1T1051 \leq T \leq 10^5 を満たす整数
  • TT 以下の任意の正整数 tt に対し、
    • BtB_t2Bt1062 \leq B_t \leq 10^6 を満たす整数
    • NtN_t0Nt0 \leq N_t かつ BtNt106B_t^{N_t} \leq 10^6 を満たす整数
    • MtM_t0Mt10180 \leq M_t \leq 10^{18} を満たす整数

出力

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

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

 

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

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

サンプル

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

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

  1. 0a<10 \leq a < 1 である。
  2. 次の条件を満たす非負整数 n0n_0 が存在する:
    • n0n_0 以上の任意の非負整数 nn に対し 01+2na(mod2n)0 \equiv 1 + 2^n a \pmod{2^n} である。

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

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

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

  1. 0a<10 \leq a < 1 である。
  2. 次の条件を満たす非負整数 n0n_0 が存在する:
    • n0n_0 以上の任意の非負整数 nn に対し 11+2na(mod2n)1 \equiv 1 + 2^n a \pmod{2^n} である。

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

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

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

  1. 0a<20 \leq a < 2 である。
  2. 次の条件を満たす非負整数 n0n_0 が存在する:
    • n0n_0 以上の任意の非負整数 nn に対し 11+2na(mod2n+1)1 \equiv 1 + 2^n a \pmod{2^{n+1}} である。

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

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