結果
問題 | No.950 行列累乗 |
ユーザー |
![]() |
提出日時 | 2019-12-13 03:14:16 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,208 bytes |
コンパイル時間 | 1,364 ms |
コンパイル使用メモリ | 112,828 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-26 05:30:43 |
合計ジャッジ時間 | 17,125 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 30 WA * 27 |
ソースコード
#include<iostream> #include<string> #include<algorithm> #include<vector> #include<iomanip> #include<math.h> #include<complex> #include<queue> #include<deque> #include<stack> #include<map> #include<set> #include<bitset> #include<functional> #include<assert.h> #include<numeric> using namespace std; #define Rep(i,m,n) for(int i=(int)(m) ; i < (int) (n) ; ++i ) #define rep(i,n) Rep(i,0,n) #define stop char nyaa;cin>>nyaa; using ll = long long; const int inf = 1e9 + 7; const ll INF = 1LL << 60; //const ll mod = 1e9 + 7; using P = pair<int, int>; using LP = pair<ll, ll>; ll p; typedef vector<vector<ll>> mat; typedef vector<ll> vec; mat mtmul(mat &A, mat &B) { mat C(A.size(), vec(B[0].size())); rep(i, (int)A.size()) { rep(k, (int)B.size()) { rep(j, (int)B[0].size()) { C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % p) % p; } } } return C; } mat mtpow(mat A, ll n) { mat B(A.size(), vec(A.size())); rep(i, (int)A.size()) { B[i][i] = 1; } while (n > 0) { if (n&(ll)1)B = mtmul(B, A); A = mtmul(A, A); n >>= 1; } return B; } ll dat(mat A) { ll res = A[0][0] * A[1][1] - A[0][1] * A[1][0]; res = (res%p + p) % p; return res; } ll mod_pow(ll x, ll n) { ll res = 1; while (n > 0) { if (n % 2)res = res * x%p; x = x * x%p; n >>= 1; } return res; } //a^res=b (mod p) ll ident(ll a, ll b) { if (b == 1)return p - 1; if (p <= 100000) { int tmp = 1; ll cop = a; while (cop != b) { cop = cop * a%p; tmp++; } return tmp; } ll d = sqrt(p); map<ll, int> mp; ll cop = b; ll inva = mod_pow(a, p - 2); for (int y = 0; y < d; y++) { mp[cop] = y; cop = cop * inva%p; } ll spea = mod_pow(a, d); cop = 1; for (int x = 0; x <= d; x++) { if (mp.find(cop) != mp.end()) { ll res = x * d + mp[cop]; res %= (p - 1); return res; } cop = cop * spea%p; } assert(false); return 0; } void solve() { mat A(2), B(2); cin >> p; rep(i, 2) { A[i].resize(2); rep(j, 2)cin >> A[i][j]; } rep(i, 2) { B[i].resize(2); rep(j, 2)cin >> B[i][j]; } mat cop = A; rep(i, 1000000) { if (cop == B) { cout << i + 1 << endl; return; } cop = mtmul(cop, A); } cout << -1 << endl; return; } signed main() { solve(); stop return 0; }