結果

問題 No.1287 えぬけー
コンテスト
ユーザー shotoyoo
提出日時 2020-11-13 21:52:52
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 290 ms / 2,000 ms
コード長 1,241 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 238 ms
コンパイル使用メモリ 82,596 KB
実行使用メモリ 77,184 KB
最終ジャッジ日時 2024-07-22 20:45:43
合計ジャッジ時間 2,431 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def factor(n, m=None):
    # mを与えると、高々その素因数まで見て、残りは分解せずにそのまま出力する
    f = {}
    tmp = n
    M = int(-(-n**0.5//1))+1
    if m is not None:
        M = min(m+1, M)
    for i in range(2, M+1):
        if tmp<i:
            break
        if tmp%i==0:
            cnt=0
            while tmp%i==0:
                cnt+=1
                tmp //= i
            f[i] = cnt
    if tmp!=1:
        f[tmp] = 1
    if not f:
        f[n] = 1
    return f
def gcd2(a, b):
    """a*x + b*y = gcd(a,b)なるx,yも求める
    """
    l = []
    while b:
        l.append(divmod(a,b))
        a, b = b, a%b
    x, y = 1, 0
    for aa,bb in l[::-1]:
        x, y = y, x - aa*y
    return a, x, y
def modinv(x, M):
    """素数ではないM、Mと互いに素なxに対し
    x * y == 1 mod M なるyを求める
    """
    a,xx,yy = gcd2(x,M)
    return a,xx%M

def sub(x,k):
    _,j = modinv(k, M-1)
    ans = pow(x, j, M)
    return ans
M = 10**9+7
t = int(input())
for i in range(t):
    x,k = map(int, input().split())
    print(sub(x,k))
0