結果
問題 | No.1287 えぬけー |
ユーザー | persimmon-persimmon |
提出日時 | 2021-02-16 21:21:23 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 471 ms / 2,000 ms |
コード長 | 707 bytes |
コンパイル時間 | 250 ms |
コンパイル使用メモリ | 86,964 KB |
実行使用メモリ | 91,488 KB |
最終ジャッジ日時 | 2023-10-11 11:59:22 |
合計ジャッジ時間 | 3,360 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 73 ms
71,464 KB |
testcase_01 | AC | 72 ms
71,268 KB |
testcase_02 | AC | 73 ms
71,380 KB |
testcase_03 | AC | 74 ms
71,440 KB |
testcase_04 | AC | 74 ms
71,332 KB |
testcase_05 | AC | 426 ms
89,192 KB |
testcase_06 | AC | 471 ms
91,488 KB |
testcase_07 | AC | 438 ms
89,328 KB |
testcase_08 | AC | 425 ms
88,896 KB |
ソースコード
import sys sys.setrecursionlimit(10**7) t=int(input()) cases=[list(map(int,input().split())) for _ in range(t)] mod=10**9+7 def ext_gcd(a, b): # a*x+b*y==gcd(a,b)たるgcd(a,b),x,y if b > 0: d,x,y = ext_gcd(b,a % b) return d,y,x-(a//b)*y return a,1,0 for x,k in cases: # x=n^k (mod)となるnを求める。k:奇数 <=5*10**8 # x^i=n^(i*k) (mod) # ここでi*k%(mod-1)=1なら、フェルマーの小定理より # x^i=n (mod) # となる。 # i*k%(mod-1)=1となるiを探す。 # kの制約よりkとmod-1は互いに素 # ある(i,j)があり、i*k=j*(mod-1)+1 # i*k+j*(mod-1)=1 g,i,j=ext_gcd(k,mod-1) if i<0: x=pow(x,mod-2,mod) i=abs(i) print(pow(x,i,mod))