結果

問題 No.1287 えぬけー
コンテスト
ユーザー jsaibuki1007
提出日時 2020-11-13 22:09:07
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
MLE  
実行時間 -
コード長 2,710 bytes
コンパイル時間 1,629 ms
コンパイル使用メモリ 166,868 KB
実行使用メモリ 814,592 KB
最終ジャッジ日時 2024-07-22 20:57:04
合計ジャッジ時間 6,501 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample MLE * 1 -- * 3
other -- * 5
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In static member function 'static int ArbitraryModInt::set_mod(int)':
main.cpp:21:3: warning: no return statement in function returning non-void [-Wreturn-type]
   21 |   }
      |   ^

ソースコード

diff # 

// from https://ei1333.github.io/luzhiled/snippets/math/mod-int.html
#include<bits/stdc++.h>

using namespace std;

struct ArbitraryModInt {

  int x;

  ArbitraryModInt() : x(0) {}

  ArbitraryModInt(int64_t y) : x(y >= 0 ? y % mod() : (mod() - (-y) % mod()) % mod()) {}

  static int &mod() {
    static int mod = 0;
    return mod;
  }

  static int set_mod(int md) {
    mod() = md;
  }

  ArbitraryModInt &operator+=(const ArbitraryModInt &p) {
    if((x += p.x) >= mod()) x -= mod();
    return *this;
  }

  ArbitraryModInt &operator-=(const ArbitraryModInt &p) {
    if((x += mod() - p.x) >= mod()) x -= mod();
    return *this;
  }

  ArbitraryModInt &operator*=(const ArbitraryModInt &p) {
    unsigned long long a = (unsigned long long) x * p.x;
    unsigned xh = (unsigned) (a >> 32), xl = (unsigned) a, d, m;
    asm("divl %4; \n\t" : "=a" (d), "=d" (m) : "d" (xh), "a" (xl), "r" (mod()));
    x = m;
    return *this;
  }

  ArbitraryModInt &operator/=(const ArbitraryModInt &p) {
    *this *= p.inverse();
    return *this;
  }

  ArbitraryModInt operator-() const { return ArbitraryModInt(-x); }

  ArbitraryModInt operator+(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) += p; }

  ArbitraryModInt operator-(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) -= p; }

  ArbitraryModInt operator*(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) *= p; }

  ArbitraryModInt operator/(const ArbitraryModInt &p) const { return ArbitraryModInt(*this) /= p; }

  bool operator==(const ArbitraryModInt &p) const { return x == p.x; }

  bool operator!=(const ArbitraryModInt &p) const { return x != p.x; }

  ArbitraryModInt inverse() const {
    int a = x, b = mod(), u = 1, v = 0, t;
    while(b > 0) {
      t = a / b;
      swap(a -= t * b, b);
      swap(u -= t * v, v);
    }
    return ArbitraryModInt(u);
  }

  ArbitraryModInt pow(int64_t n) const {
    ArbitraryModInt ret(1), mul(x);
    while(n > 0) {
      if(n & 1) ret *= mul;
      mul *= mul;
      n >>= 1;
    }
    return ret;
  }

  friend ostream &operator<<(ostream &os, const ArbitraryModInt &p) {
    return os << p.x;
  }

  friend istream &operator>>(istream &is, ArbitraryModInt &a) {
    int64_t t;
    is >> t;
    a = ArbitraryModInt(t);
    return (is);
  }
};

int main(void){
    int md = 1000000006;

    int T; cin >> T;
    for(int t = 0; t < T; t++){
        int X, K; cin >> X >> K;
        ArbitraryModInt::set_mod(md);
        ArbitraryModInt mK(K);
        ArbitraryModInt mKinv = mK.inverse();

        ArbitraryModInt::set_mod(md+1);
        ArbitraryModInt mX(X);
        ArbitraryModInt ans = mX.pow(mKinv.x);
        cout << ans << endl;
    }
    return 0;
}
0