結果

問題 No.1287 えぬけー
コンテスト
ユーザー legosuke
提出日時 2020-11-15 07:13:19
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 286 ms / 2,000 ms
コード長 1,366 bytes
コンパイル時間 2,053 ms
コンパイル使用メモリ 193,348 KB
最終ジャッジ日時 2025-01-16 00:45:19
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#line 1 "test/01_Math/01_NumberTheory/04.01_yukicoder-1287.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1287"

#line 1 "template/template.cpp"
#include <bits/stdc++.h>
using namespace std;
#line 4 "test/01_Math/01_NumberTheory/04.01_yukicoder-1287.test.cpp"

#line 1 "01_Math/01_NumberTheory/04.01_ext-gcd.cpp"
/**
 * @brief 拡張 Euclid 互助法
 * @docs docs/ext-gcd.md
 */
long long ext_gcd(long long a, long long b, long long& x, long long& y) {
    if (b == 0) {
        x = 1; y = 0;
        return a;
    }
    auto q = a / b;
    auto g = ext_gcd(b, a - q * b , x, y);
    auto z = x - q * y;
    x = y; y = z;
    return g;
}
#line 1 "01_Math/02_Combinatorics/01.01_mod-pow.cpp"
/**
 * @brief 累乗
 * @docs docs/mod-pow.md
 */
long long mod_pow(long long a, long long n, long long m) {
    a %= m; if (a < 0) a += m;
    long long res = 1 % m;
    while (n) {
        if (n & 1) res = res * a % m;
        a = a * a % m;
        n >>= 1;
    }
    return res;
}
#line 7 "test/01_Math/01_NumberTheory/04.01_yukicoder-1287.test.cpp"

int main() {
    const long long MOD = 1000000007;
    int T;
    cin >> T;
    for (int i = 0; i < T; ++i) {
        long long X, K, x, y;
        cin >> X >> K;
        ext_gcd(MOD - 1, K, x, y);
        y %= (MOD - 1);
        if (y < 0) y += MOD - 1;
        cout << mod_pow(X, y, MOD) << endl;
    }
}
0