結果

問題 No.1287 えぬけー
ユーザー pazzle1230
提出日時 2020-11-13 21:50:08
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 198 ms / 2,000 ms
コード長 2,183 bytes
コンパイル時間 1,596 ms
コンパイル使用メモリ 168,444 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-07-22 20:42:48
合計ジャッジ時間 3,182 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define INF_LL (int64)1e18
#define INF (int32)1e9
#define REP(i, n) for(int64 i = 0;i < (n);i++)
#define FOR(i, a, b) for(int64 i = (a);i < (b);i++)
#define all(x) x.begin(),x.end()
#define fs first
#define sc second

using int32 = int_fast32_t;
using uint32 = uint_fast32_t;
using int64 = int_fast64_t;
using uint64 = uint_fast64_t;
using PII = pair<int32, int32>;
using PLL = pair<int64, int64>;

const double eps = 1e-10;

template<typename A, typename B>inline void chmin(A &a, B b){if(a > b) a = b;}
template<typename A, typename B>inline void chmax(A &a, B b){if(a < b) a = b;}

template<typename T>
vector<T> make_v(size_t a){return vector<T>(a);}

template<typename T,typename... Ts>
auto make_v(size_t a,Ts... ts){
	return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));
}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value!=0>::type
fill_v(U &u,const V... v){u=U(v...);}

template<typename T,typename U,typename... V>
typename enable_if<is_same<T, U>::value==0>::type
fill_v(U &u,const V... v){
	for(auto &e:u) fill_v<T>(e,v...);
}

::std::pair<::std::int64_t, ::std::int64_t> extgcd(::std::int64_t a, ::std::int64_t b) {
  ::std::pair<::std::int64_t, ::std::int64_t> pa(1, 0), pb(0, 1);
  while (b != 0) {
    ::std::swap(a, b); ::std::swap(pa, pb);
    pb = ::std::make_pair(pb.first - pa.first * (b / a), pb.second - pa.second * (b / a));
    b = b % a;
  }
  return pa;
}



// return a^-1 mod (mod)
// O(log mod)
//
// Require -> extgcd
::std::int64_t modinv(::std::int64_t a, ::std::int64_t mod) {
  ::std::int64_t x = extgcd(a, mod).first;
  if (x < 0) x += mod;
  return x;
}

// return a^b mod (mod)
// O(log mod)
::std::int64_t modpow(::std::int64_t a, ::std::int64_t b, ::std::int64_t mod) {
  ::std::int64_t res = 1;
  while (b > 0) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
    b >>= 1;
  }
  return res;
}


void solve() {
  int64 X, K;
  cin >> X >> K;
  int64 Kinv = modinv(K, 1e9+6);
  cout << modpow(X, Kinv, 1e9+7) << endl;
}

int main(void) {
  cin.tie(0);
  ios::sync_with_stdio(false);

  int64 T;
  cin >> T;
  REP(_, T) {
    solve();
  }
}
0