#408325 (C++14) No.950 行列累乗

提出ソース

結果

問題	No.950 行列累乗
ユーザー	risujiroh
提出日時	2019-12-13 23:07:04
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	RE
実行時間	-
コード長	7,527 bytes
コンパイル時間	2,189 ms
コンパイル使用メモリ	190,040 KB
実行使用メモリ	4,504 KB
最終ジャッジ日時	2023-09-10 04:42:46
合計ジャッジ時間	9,924 ms
ジャッジサーバーID （参考情報）	judge12 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	RE	-
testcase_01	RE	-
testcase_02	RE	-
testcase_03	AC	1 ms 4,376 KB
testcase_04	RE	-
testcase_05	RE	-
testcase_06	RE	-
testcase_07	WA	-
testcase_08	RE	-
testcase_09	RE	-
testcase_10	RE	-
testcase_11	WA	-
testcase_12	AC	2 ms 4,380 KB
testcase_13	RE	-
testcase_14	RE	-
testcase_15	RE	-
testcase_16	RE	-
testcase_17	RE	-
testcase_18	AC	2 ms 4,384 KB
testcase_19	RE	-
testcase_20	RE	-
testcase_21	RE	-
testcase_22	RE	-
testcase_23	RE	-
testcase_24	RE	-
testcase_25	RE	-
testcase_26	RE	-
testcase_27	AC	1 ms 4,384 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	AC	2 ms 4,376 KB
testcase_37	RE	-
testcase_38	RE	-
testcase_39	AC	2 ms 4,376 KB
testcase_40	RE	-
testcase_41	RE	-
testcase_42	RE	-
testcase_43	RE	-
testcase_44	RE	-
testcase_45	RE	-
testcase_46	RE	-
testcase_47	RE	-
testcase_48	RE	-
testcase_49	RE	-
testcase_50	RE	-
testcase_51	RE	-
testcase_52	RE	-
testcase_53	RE	-
testcase_54	RE	-
testcase_55	RE	-
testcase_56	RE	-
testcase_57	RE	-
testcase_58	RE	-
testcase_59	RE	-
testcase_60	RE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

long long mod = 998244353;
struct Mint {
  long long v;
  Mint(long long a = 0) : v((a %= mod) < 0 ? a + mod : a) {}
  Mint operator-() const { return 0 - *this; }
  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); }
};

Mint alpha;
struct Cint {
  Mint a, b;
  Cint(Mint _a = 0, Mint _b = 0) : a(_a), b(_b) {}
  Cint(long long _a) : a(_a), b(0) {}
  Cint operator-() const { return {-a, -b}; }
  Cint& operator*=(Cint r) {
    return *this = {a * r.a + alpha * b * r.b, a * r.b + b * r.a};
  }
  Cint& operator/=(Cint r) { return *this *= r.inv(); }
  Cint& operator+=(Cint r) { a += r.a, b += r.b; return *this; }
  Cint& operator-=(Cint r) { a -= r.a, b -= r.b; return *this; }
  friend Cint operator*(Cint l, Cint r) { return l *= r; }
  friend Cint operator/(Cint l, Cint r) { return l /= r; }
  friend Cint operator+(Cint l, Cint r) { return l += r; }
  friend Cint operator-(Cint l, Cint r) { return l -= r; }
  Cint pow(long long n) const {
    Cint res = {1, 0};
    for (Cint t = *this; n; t *= t, n >>= 1) if (n & 1) res *= t;
    return res;
  }
  Cint inv() const {
    Mint den = a * a - alpha * b * b;
    return {a / den, -b / den};
  }
  friend string to_string(Cint c) { return "(" + to_string(c.a) + ", " + to_string(c.b) + ")"; }
};
bool operator<(Cint l, Cint r) { return make_pair(l.a.v, l.b.v) < make_pair(r.a.v, r.b.v); }
bool operator==(Cint l, Cint r) { return l.a.v == r.a.v and l.b.v == r.b.v; }

template <class T> using Mat = array< array<T, 2>, 2 >;

template <class T> Mat<T> operator*(Mat<T> A, Mat<T> B) {
  Mat<T> res;
  for (int i : {0, 1}) {
    for (int k : {0, 1}) {
      for (int j : {0, 1}) {
        res[i][j] += A[i][k] * B[k][j];
      }
    }
  }
  return res;
}
template <class T> Mat<T>& operator*=(Mat<T>& A, Mat<T> B) { return A = A * B; }
template <class T> Mat<T> pow(Mat<T> A, long long n) {
  Mat<T> res = {1, 0, 0, 1};
  while (n) {
    if (n & 1) {
      res *= A;
    }
    A *= A;
    n >>= 1;
  }
  return res;
}
template <class T> Mat<T> inv(Mat<T> A) {
  Mat<T> res{
    A[1][1], -A[0][1],
    -A[1][0], A[0][0]
  };
  T 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;
}
istream& operator>>(istream& is, Mat<Mint>& A) {
  for (int i : {0, 1}) {
    for (int j : {0, 1}) {
      is >> A[i][j].v;
    }
  }
  return is;
}

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_inv(long long a, long long p) {
  a = tmod(a, p);
  long long b = p, x = 1, u = 0;
  while (b) {
    long long q = a / b;
    swap(a -= q * b, b);
    swap(x -= q * u, u);
  }
  return a == 1 ? tmod(x, p) : -1;
}
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);
}

// 解の存在を判定し， p をどの2つも互いに素にする
bool pre(vector<long long>& a, vector<long long>& p) {
  assert(a.size() == p.size());
  int n = a.size();
  for (int i = 0; i < n; ++i) {
    a[i] = tmod(a[i], p[i]);
  }
  for (int i = 0; i < n; ++i) for (int j = i + 1; j < n; ++j) {
    long long d = __gcd(p[i], p[j]);
    if (a[i] % d != a[j] % d) return false;
    p[i] /= d;
    p[j] /= d;
    while (true) {
      long long e = __gcd(d, p[j]);
      if (e == 1) break;
      p[j] *= e;
      d /= e;
    }
    p[i] *= d;
    a[i] %= p[i];
    a[j] %= p[j];
  }
  return true;
}
long long CRT(const vector<long long>& a, const vector<long long>& p) {
  int n = a.size();
  long long x = 0;
  vector<long long> y(n);
  long long prod = 1;
  for (int i = 0; i < n; ++i) {
    y[i] = tmod(a[i] - x, p[i]);
    for (int j = 0; j < i; ++j) {
      (y[i] *= mod_inv(p[j], p[i])) %= p[i];
    }
    x += prod * y[i];
    prod *= p[i];
  }
  return x;
}

Cint sqrt(Mint a) {
  auto r = mod_sqrt(a.v, mod);
  if (r != -1) {
    return {r, 0};
  }
  return {0, mod_sqrt((a / alpha).v, mod)};
}
long long ord(Cint a) {
  set<long long> se;
  for (long long n : {mod - 1, mod + 1}) {
    for (long long i = 2; i * i <= n; ++i) {
      while (n % i == 0) {
        se.insert(i);
        n /= i;
      }
    }
  }
  long long res = mod * mod - 1;
  for (long long p : se) {
    while (res % p == 0 and a.pow(res / p) == 1) {
      res /= p;
    }
  }
  return res;
}
long long log(Cint a, Cint b) {
  long long m = ceil(sqrt(mod * mod - 1));
  map<Cint, long long> mp;
  Cint t = 1;
  for (long long j = 0; j < m; ++j) {
    mp[t] = j;
    t *= a;
  }
  a = a.pow(m).inv(), t = 1;
  for (long long i = 0; i < (mod * mod - 1 + m - 1) / m; ++i) {
    if (mp.count(t * b)) {
      return i * m + mp[t * b];
    }
    t *= a;
  }
  return -1;
}

int main() {
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
  cin >> mod;
  Mat<Cint> A, B;
  for (int i : {0, 1}) {
    for (int j : {0, 1}) {
      cin >> A[i][j].a.v;
    }
  }
  for (int i : {0, 1}) {
    for (int j : {0, 1}) {
      cin >> B[i][j].a.v;
    }
  }
  Cint tr = A[0][0] + A[1][1];
  Cint det = A[0][0] * A[1][1] - A[0][1] * A[1][0];
  Cint d = tr * tr - 4 * det;
  Cint t = sqrt(d.a);
  Cint lambda[2];
  lambda[0] = (tr + t) / 2;
  lambda[1] = (tr - t) / 2;
  Mat<Cint> P;
  for (int k = 0; k < 2; ++k) {
    auto nA = A;
    for (int i : {0, 1}) {
      nA[i][i] -= lambda[k];
    }
    if (nA[0][1] == Cint(0, 0)) {
      P[1][k] = {1, 0};
    } else {
      P[0][k] = {1, 0};
      P[1][k] = -nA[0][0] / nA[0][1];
    }
  }
  Mat<Cint> D{lambda[0], 0, 0, lambda[1]};
  B = inv(P) * B * P;
  if (!(B[0][1] == 0) or !(B[1][0] == 0)) {
    cout << "-1\n";
    return 0;
  }
  assert(mod * mod <= 1e12);
  vector<long long> x(2), ps(2);
  for (int k : {0, 1}) {
    x[k] = log(D[k][k], B[k][k]);
    if (x[k] == -1) {
      cout << "-1\n";
      return 0;
    }
    ps[k] = ord(D[k][k]);
    x[k] %= ps[k];
  }
  if (not pre(x, ps)) {
    cout << "-1\n";
    return 0;
  }
  long long res = CRT(x, ps);
  if (res == 0) {
    res += ps[0] * ps[1];
  }
  cout << res << '\n';
}

yukicoder

結果

テストケース

ソースコード