結果

問題 No.950 行列累乗
コンテスト
ユーザー risujiroh
提出日時 2019-12-13 01:03:31
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
RE  
実行時間 -
コード長 4,448 bytes
コンパイル時間 2,131 ms
コンパイル使用メモリ 188,420 KB
実行使用メモリ 7,040 KB
最終ジャッジ日時 2024-06-26 02:08:35
合計ジャッジ時間 10,016 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1 RE * 3
other AC * 10 WA * 1 RE * 46
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

string to_string(string s) { return '"' + s + '"'; }
string to_string(bool b) { return b ? "true" : "false"; }
template <size_t N> string to_string(bitset<N> bs) {
  string res;
  for (size_t i = 0; i < N; ++i) res += '0' + bs[i];
  return res;
}
string to_string(vector<bool> v) {
  string res = "{";
  for (bool e : v) res += to_string(e) + ", ";
  return res += "}";
}

template <class T, class U> string to_string(pair<T, U> p);
template <class C> string to_string(C c) {
  string res = "{";
  for (auto e : c) res += to_string(e) + ", ";
  return res += "}";
}
template <class T, class U> string to_string(pair<T, U> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

void debug() { cerr << '\n'; }
template <class Head, class... Tail> void debug(Head head, Tail... tail) {
  cerr << ' ' << to_string(head), debug(tail...);
}
#ifdef LOCAL
#define DEBUG(...) cerr << "[" << #__VA_ARGS__ << "]:", debug(__VA_ARGS__)
#else
#define DEBUG(...)
#endif

long long mod;
struct Mint {
  long long v;
  Mint(long long a = 0) : v((a %= mod) < 0 ? a + mod : a) {}
  Mint& operator*=(Mint r) { v = 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{0, 0, 0, 0};
  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, A);
  }
  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