結果

問題 No.950 行列累乗
コンテスト
ユーザー risujiroh
提出日時 2019-12-13 00:50:21
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,035 bytes
コンパイル時間 2,067 ms
コンパイル使用メモリ 185,560 KB
実行使用メモリ 6,948 KB
最終ジャッジ日時 2024-06-26 01:51:48
合計ジャッジ時間 9,779 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1 RE * 3
other AC * 4 WA * 9 RE * 44
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

int mod;
struct Mint {
  int v;
  Mint(long long a = 0) : v((a %= mod) < 0 ? a + mod : a) {}
  Mint& operator*=(Mint r) { v = (long long)v * r.v % mod; return *this; }
  Mint& operator/=(Mint r) { return *this *= r.inv(); }
  Mint& operator+=(Mint r) { if ((v += r.v) >= mod) v -= mod; return *this; }
  Mint& operator-=(Mint r) { if ((v -= r.v) < 0) v += mod; return *this; }
  friend Mint operator*(Mint l, Mint r) { return l *= r; }
  friend Mint operator/(Mint l, Mint r) { return l /= r; }
  friend Mint operator+(Mint l, Mint r) { return l += r; }
  friend Mint operator-(Mint l, Mint r) { return l -= r; }
  Mint pow(long long n) const {
    assert(n >= 0);
    Mint res = 1;
    for (Mint t = *this; n; t *= t, n >>= 1) if (n & 1) res *= t;
    return res;
  }
  Mint inv() const { assert(v); return pow(mod - 2); }
  friend string to_string(Mint a) { return to_string(a.v); }
};
bool operator<(Mint l, Mint r) { return l.v < r.v; }

long long tmod(long long a, long long b) { 
  if (b < 0) return -tmod(-a, -b);
  return (a %= b) < 0 ? a + b : a;
}
long long tdiv(long long a, long long b) { return (a - tmod(a, b)) / b; }
long long mod_pow(long long a, long long n, long long p) {
  assert(n >= 0);
  a = tmod(a, p);
  long long res = 1;
  while (n) {
    if (n & 1) (res *= a) %= p;
    (a *= a) %= p;
    n >>= 1;
  }
  return res;
}
long long mod_sqrt(long long a, long long p) {
  if (!a or p == 2) return a;
  if (mod_pow(a, (p - 1) / 2, p) != 1) {
    return -1;
  }
  long long d = p - 1;
  while (d % 2 == 0) d /= 2;
  long long x = mod_pow(a, (d + 1) / 2, p), y = mod_pow(a, d, p), z = -1;
  for (long long g = 2; g < p; ++g) if (mod_pow(g, (p - 1) / 2, p) != 1) {
    z = mod_pow(g, d, p);
    break;
  }
  for (int k = __lg((p - 1) / d) - 1; k; --k) {
    if (mod_pow(y, 1 << (k - 1), p) != 1) {
      x = x * z % p;
      y = y * z % p * z % p;
    }
    z = z * z % p;
  }
  return min(x, p - x);
}

using Mat = array< array<Mint, 2>, 2>;

Mat mul(Mat A, Mat B) {
  Mat C;
  for (int i : {0, 1}) {
    for (int k : {0, 1}) {
      for (int j : {0, 1}) {
        C[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  return C;
}
Mat pow(Mat a, long long n) {
  Mat res{1, 0, 0, 1};
  while (n) {
    if (n & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    n >>= 1;
  }
  return res;
}
Mat inv(Mat A) {
  Mat res{
    A[1][1], 0 - A[0][1],
    0 - A[1][0], A[0][0]
  };
  Mint det = A[0][0] * A[1][1] - A[0][1] * A[1][0];
  for (int i : {0, 1}) {
    for (int j : {0, 1}) {
      res[i][j] /= det;
    }
  }
  return res;
}
int mat_log(Mat A, Mat B) {
  int m = ceil(sqrt(mod - 1));
  map<Mat, int> mp;
  Mat a{1, 0, 0, 1};
  for (int j = 0; j < m; ++j) {
    mp[a] = j;
    a = mul(a, A);
  }
  A = inv(pow(A, m)), a = {1, 0, 0, 1};
  for (int i = 0; i < (mod - 1 + m - 1) / m; ++i) {
    if (mp.count(mul(a, B))) {
      return i * m + mp[mul(a, B)];
    }
    a = mul(a, B);
  }
  return -1;
}
// g固定のときは前処理を1回だけにしてmを大きめ（sqrt(|query|*p)くらい？）にする
// lint mod_log(lint g, lint x, lint p) {
//   g = tmod(g, p);
//   x = tmod(x, p);
//   int m = ceil(sqrt(p - 1));
//   map<int, int> mp;
//   lint a = 1;
//   for (int j = 0; j < m; ++j) {
//     mp[a] = j;
//     (a *= g) %= p;
//   }
//   g = mod_inv(mod_pow(g, m, p), p), a = 1;
//   for (int i = 0; i < (p - 1 + m - 1) / m; ++i) {
//     if (mp.count(a * x % p)) {
//       return i * m + mp[a * x % p];
//     }
//     (a *= g) %= p;
//   }
//   return -1;
// }


int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cin >> mod;
  Mat A, B;
  for (int i : {0, 1}) {
    for (int j : {0, 1}) {
      cin >> A[i][j].v;
    }
  }
  for (int i : {0, 1}) {
    for (int j : {0, 1}) {
      cin >> B[i][j].v;
    }
  }
  Mint tr = A[0][0] + A[1][1];
  Mint det = A[0][0] * A[1][1] - A[0][1] * A[1][0];
  auto t = mod_sqrt((tr * tr - 4 * det).v, mod);
  assert(t != -1);
  assert(t != 0);
  assert(det.v);
  cout << mat_log(A, B) << '\n';
}
0