結果

問題 No.950 行列累乗
ユーザー risujirohrisujiroh
提出日時 2019-12-13 01:19:23
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
RE  
実行時間 -
コード長 5,294 bytes
コンパイル時間 2,309 ms
コンパイル使用メモリ 185,116 KB
実行使用メモリ 6,868 KB
最終ジャッジ日時 2023-09-08 09:27:58
合計ジャッジ時間 55,793 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 1,007 ms
4,376 KB
testcase_04 AC 1,006 ms
4,376 KB
testcase_05 AC 2 ms
4,376 KB
testcase_06 AC 1,007 ms
4,380 KB
testcase_07 AC 3 ms
4,376 KB
testcase_08 AC 177 ms
4,376 KB
testcase_09 AC 1,006 ms
4,380 KB
testcase_10 AC 3 ms
4,380 KB
testcase_11 AC 2 ms
4,380 KB
testcase_12 AC 1,006 ms
4,376 KB
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 1,006 ms
4,380 KB
testcase_16 AC 117 ms
4,376 KB
testcase_17 AC 1 ms
4,376 KB
testcase_18 AC 1,005 ms
4,380 KB
testcase_19 AC 1 ms
4,380 KB
testcase_20 AC 2 ms
4,380 KB
testcase_21 RE -
testcase_22 RE -
testcase_23 AC 1,033 ms
6,132 KB
testcase_24 RE -
testcase_25 AC 1,027 ms
5,316 KB
testcase_26 AC 1,030 ms
6,280 KB
testcase_27 AC 1,036 ms
5,896 KB
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 AC 1,036 ms
6,868 KB
testcase_41 AC 1,034 ms
6,856 KB
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 AC 2 ms
4,380 KB
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 AC 2 ms
4,376 KB
testcase_55 AC 1 ms
4,380 KB
testcase_56 RE -
testcase_57 AC 2 ms
4,380 KB
testcase_58 AC 2 ms
4,376 KB
testcase_59 RE -
testcase_60 RE -
権限があれば一括ダウンロードができます

ソースコード

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

struct Stopwatch {
  clock_t t = clock();
  void restart() { t = clock(); }
  int elapsed() const { return (clock() - t) * 1000 / CLOCKS_PER_SEC; }
  friend string to_string(Stopwatch sw) {
    return "Time: " + to_string(sw.elapsed()) + " ms";
  }
} sw;

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; }
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];
  assert(det.v);
  for (int i : {0, 1}) {
    for (int j : {0, 1}) {
      res[i][j] /= det;
    }
  }
  return res;
}
long long mat_ord(Mat A) {
  long long res = mod - 1;
  for (int i = 2; i * i <= res; ++i) {
    while (res % i == 0 and pow(A, res / i) == Mat{1, 0, 0, 1}) {
      res /= i;
    }
  }
  return res;
}
long long mat_log(Mat A, Mat B) {
  long long m = ceil(sqrt(mod - 1));
  map<Mat, long long> 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 (long long i = 0; i < (mod - 1 + m - 1) / m; ++i) {
    if (mp.count(mul(a, B))) {
      long long res = i * m + mp[mul(a, B)];
      if (res == 0) {
        res = mat_ord(A);
      }
      return res;
    }
    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;
    }
  }
  int n = 1;
  Mat C = A;
  while (sw.elapsed() < 1000) {
    if (C == B) {
      cout << n << '\n';
      return 0;
    }
    C = mul(C, A);
    ++n;
  }
  if (mod < n) {
    cout << "-1\n";
    return 0;
  }
  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