結果
問題 | No.1287 えぬけー |
ユーザー |
|
提出日時 | 2021-02-16 21:15:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,790 ms / 2,000 ms |
コード長 | 737 bytes |
コンパイル時間 | 277 ms |
コンパイル使用メモリ | 87,384 KB |
実行使用メモリ | 389,304 KB |
最終ジャッジ日時 | 2023-10-11 11:53:36 |
合計ジャッジ時間 | 8,827 ms |
ジャッジサーバーID (参考情報) |
judge11 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 74 ms
71,476 KB |
testcase_01 | AC | 75 ms
71,216 KB |
testcase_02 | AC | 75 ms
71,408 KB |
testcase_03 | AC | 72 ms
71,032 KB |
testcase_04 | AC | 75 ms
71,036 KB |
testcase_05 | AC | 1,706 ms
373,628 KB |
testcase_06 | AC | 1,655 ms
373,412 KB |
testcase_07 | AC | 1,681 ms
389,304 KB |
testcase_08 | AC | 1,790 ms
374,796 KB |
ソースコード
import sys sys.setrecursionlimit(10**7) t=int(input()) cases=[list(map(int,input().split())) for _ in range(t)] mod=10**9+7 memo={} def ext_gcd(a, b): # a*x+b*y==gcd(a,b)たるgcd(a,b),x,y if (a,b) in memo:return memo[(a,b)] if b > 0: d,x,y = ext_gcd(b,a % b) memo[(a,b)]=d,y,x-(a//b)*y 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) print(pow(x,i,mod))