結果

問題 No.3170 [Cherry 7th Tune KY] Even if you could say "See you ..."
ユーザー HoyHoyCharhang
提出日時 2025-05-31 00:10:18
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 7,346 bytes
コンパイル時間 4,115 ms
コンパイル使用メモリ 298,584 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-05-31 00:10:25
合計ジャッジ時間 6,648 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19 WA * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define fi first
#define se second
#define rep(i,s,n) for (int i = (s); i < (n); ++i)
#define rrep(i,n,g) for (int i = (n)-1; i >= (g); --i)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
#define len(x) (int)(x).size()
#define dup(x,y) (((x)+(y)-1)/(y))
#define pb push_back
#define eb emplace_back
#define Field(T) vector<vector<T>>
using namespace std;
using ll = long long;
using ull = unsigned long long;
template<typename T> using pq = priority_queue<T,vector<T>,greater<T>>;
using P = pair<int,int>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}

struct ArbitraryModInt {
  int x;
  ArbitraryModInt() : x(0) {}
  ArbitraryModInt(int64_t y) : x(y >= 0 ? y % get_mod() : (get_mod() - (-y) % get_mod()) % get_mod()) {}

  static int &get_mod() {
    static int mod = 0;
    return mod;
  }
  static void set_mod(int md) {
    get_mod() = md;
  }

  ArbitraryModInt &operator+=(const ArbitraryModInt &p) {
    if((x += p.x) >= get_mod()) x -= get_mod();
    return *this;
  }
  ArbitraryModInt &operator-=(const ArbitraryModInt &p) {
    if((x += get_mod() - p.x) >= get_mod()) x -= get_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" (get_mod()));
    x = m;
    return *this;
  }
  ArbitraryModInt &operator/=(const ArbitraryModInt &p) {
    *this *= p.inv();
    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 inv() const {
    int a = x, b = get_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);
  }
};

using mint = ArbitraryModInt;

template<typename T>
vector<vector<T>> mat_mul(vector<vector<T>> &a, vector<vector<T>> &b) {
  assert(b.size() == a[0].size());
  int n = (int)a.size(), m = (int)b[0].size(), l = (int)b.size();
  vector<vector<T>> c(n, vector<T>(m, T(0)));
  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < m; ++j) {
      for (int k = 0; k < l; ++k) {
        c[i][j] += a[i][k] * b[k][j];
      }
    }
  }
  return c;
}

// input  : a, M (0 < a < M)
// output : pair(g, x) s.t. g = gcd(a, M), xa = g (mod M), 0 <= x < b/g
template <typename uint>
pair<uint, uint> gcd_inv(uint a, uint M) {
  assert(M != 0 && 0 < a);
  a %= M;
  uint b = M, s = 1, t = 0;
  while (true) {
    if (a == 0) return {b, t + M};
    t -= b / a * s;
    b %= a;
    if (b == 0) return {a, s};
    s -= a / b * t;
    a %= b;
  }
}

// 入力 : 0 <= rem[i] < mod[i], 1 <= mod[i]
// 存在するとき   : return {rem, mod}
// 存在しないとき : return {0, 0}
template <typename T, typename U>
pair<unsigned long long, unsigned long long> garner(const vector<T>& rem,
                                                    const vector<U>& mod) {
  assert(rem.size() == mod.size());
  using u64 = unsigned long long;
  u64 r0 = 0, m0 = 1;
  for (int i = 0; i < (int)rem.size(); i++) {
    assert(1 <= mod[i]);
    assert(0 <= rem[i] && rem[i] < mod[i]);
    u64 m1 = mod[i], r1 = rem[i] % m1;
    if (m0 < m1) swap(r0, r1), swap(m0, m1);
    if (m0 % m1 == 0) {
      if (r0 % m1 != r1) return {0, 0};
      continue;
    }
    u64 g, im;
    tie(g, im) = gcd_inv(m0, m1);
    u64 y = r0 < r1 ? r1 - r0 : r0 - r1;
    if (y % g != 0) return {0, 0};
    u64 u1 = m1 / g;
    y = y / g % u1;
    if (r0 > r1 && y != 0) y = u1 - y;
    u64 x = y * im % u1;
    r0 += x * m0;
    m0 *= u1;
  }
  return {r0, m0};
}

void solve() {
  int m;
  cin >> m;
  mint::set_mod(m);
  vector<vector<mint>> a(2, vector<mint>(2)), b(2, vector<mint>(2));
  rep(i,0,2) rep(j,0,2) cin >> a[i][j];
  rep(i,0,2) rep(j,0,2) cin >> b[i][j];
  int l = -1;
  rep(i,0,m) {
    if ((-a[0][0]+i)*(-a[1][1]+i) == a[0][1]*a[1][0]) {
      l = i;
      break;
    }
  }
  vector<vector<mint>> p(2, vector<mint>(2, 0)), q(2, vector<mint>(2, 0));
  p[0][0] = a[0][1], p[1][0] = -(a[0][0]-l);
  if (p[0][0] == 0 && p[1][0] == 0) p[0][0] = p[1][0] = 1;
  if (p[0][0] != 0) p[1][1] = p[0][0].inv(), p[0][1] = 0;
  else p[1][1] = 0, p[0][1] = -p[1][0].inv();
  q[0][0] = p[1][1], q[0][1] = -p[0][1], q[1][0] = -p[1][0], q[1][1] = p[0][0];
  // cout << "p = " << endl;
  // rep(i,0,2) {
  //   rep(j,0,2) {
  //     cout << p[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  a = mat_mul(q, a);
  a = mat_mul(a, p);
  b = mat_mul(q, b);
  b = mat_mul(b, p);
  // rep(i,0,2) {
  //   rep(j,0,2) {
  //     cout << a[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  // rep(i,0,2) {
  //   rep(j,0,2) {
  //     cout << b[i][j] << " ";
  //   }
  //   cout << endl;
  // }
  if (b[1][0] != 0) {
    cout << -1 << endl;
    return;
  }
  if (a[0][1] == 0) {
    if (b[0][1] != 0) {
      cout << -1 << endl;
      return;
    }
    mint v = 1, w = 1;
    rep(i,0,m+2) {
      if (v == b[0][0] && w == b[1][1]) {
        cout << i << endl;
        return;
      }
      v *= a[0][0], w *= a[1][1];
    }
    cout << -1 << endl;
    return;
  } else if (a[0][0] != a[1][1]) {
    vector<vector<mint>> x(2, vector<mint>(2));
    x[0][0] = x[1][1] = 1;
    rep(i,0,m+2) {
      if (x == b) {
        cout << i << endl;
        return;
      }
      x = mat_mul(x, a);
    }
    cout << -1 << endl;
  } else {
    if (b[0][0] != b[1][1]) {
      cout << -1 << endl;
      return;
    }
    if (a[0][0] == 0) {
      vector<vector<mint>> x(2, vector<mint>(2));
      x[0][0] = x[1][1] = 1;
      rep(i,0,4) {
        if (x == b) {
          cout << i << endl;
          return;
        }
        x = mat_mul(x, a);
      }
      cout << -1 << endl;
    }
    int r = -1, v = -1;
    mint c = 1;
    rep(i,0,m+2) {
      if (c == b[0][0]) {
        r = i;
      }
      c *= a[0][0];
      if (c == 1) {
        v = i+1;
        break;
      }
    }
    if (r == -1) {
      cout << -1 << endl;
      return;
    }
    // cout << v << " " << r << " " << a[0][0].pow(v) << endl;
    auto [ans, mod] = garner(vector<ll>({r, (a[0][0]*b[0][1]/(a[0][1]*b[0][0])).x}), vector<ll>({v, m}));
    cout << ans << endl;
  }
}

int main() {
  int t;
  cin >> t;
  while(t--) solve();
  return 0;
}
0