結果

問題 No.3170 [Cherry 7th Tune KY] Even if you could say "See you ..."
コンテスト
ユーザー ymm-knight
提出日時 2025-06-11 15:02:02
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
(最新)
AC  
(最初)
実行時間 -
コード長 4,165 bytes
コンパイル時間 2,117 ms
コンパイル使用メモリ 227,832 KB
実行使用メモリ 50,912 KB
最終ジャッジ日時 2025-06-11 23:07:15
合計ジャッジ時間 9,292 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 39 WA * 1
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
#define Loop(x,l,r) for (ll x = ll(l); x < ll(r); ++x)
#define LoopR(x,l,r) for (ll x = ll(r)-1; x >= ll(l); --x)
#define Looc(x,l,r) for (ll x = ll(l); x <= ll(r); ++x)
#define LoocR(x,l,r) for (ll x = ll(r); x >= ll(l); --x)
//#define int ll
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#ifndef DB
#define DB 0
#define endl '\n'
#endif
#define debugl(l) if constexpr ((l) < DB)
#define debug debugl(0)

struct custom_hash {
	static uint64_t splitmix64(uint64_t x) {
		// http://xorshift.di.unimi.it/splitmix64.c
		x += 0x9e3779b97f4a7c15;
		x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		return x ^ (x >> 31);
	}
	size_t operator()(uint64_t x) const {
		static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		return splitmix64(x + FIXED_RANDOM);
	}
};

template<class T>
using better_map = __gnu_pbds::gp_hash_table<ll, T, custom_hash>;


int mod;

ll pw(ll x, ll y) {
	ll a = 1;
	while (y) {
		if (y%2)
			a = a*x % mod;
		x = x*x % mod;
		y /= 2;
	}
	return a;
}
ll inv(ll x) { return pw(x, mod-2); }

struct Mat : array<ll, 4> {
	Mat operator*(const Mat &m) const {
		return {
			(at(0) * m[0] + at(1) * m[2]) % mod,
			(at(0) * m[1] + at(1) * m[3]) % mod,
			(at(2) * m[0] + at(3) * m[2]) % mod,
			(at(2) * m[1] + at(3) * m[3]) % mod,
		};
	}
	Mat &operator*=(const Mat &m) {
		return *this = *this * m;
	}
	ll det() const {
		return ((at(0) * at(3) - at(1) * at(2))%mod+mod)%mod;
	}
	Mat inv() const {
		return Mat{
			at(3),
			(mod - at(1)) % mod,
			(mod - at(2)) % mod,
			at(0),
		} * ::inv(det());
	}
	pll up  () const { return {at(0), at(1)}; }
	pll down() const { return {at(2), at(3)}; }
	
	Mat operator*(ll d) const {
		Mat ans = *this;
		for (auto &x : ans)
			x = x * d % mod;
		return ans;
	}
};

pll operator*(const pll &v, const Mat &m) {
	Mat vm = {
		v.first,
		v.second,
		0,
		0,
	};
	vm *= m;
	return {vm[0], vm[1]};
}

const Mat I = {1, 0, 0, 1};
Mat A, B, Ap;

better_map<ll> up;

ll mypair(int x, int y) { return ((ll)x << 32) ^ y; }
ll mypair(pll p) { return mypair((int)p.first, (int)p.second); }

void solve_det0()
{
	int p = 0;
	Mat m = I;
	while (p < mod + 10 && m != B) {
		m *= A;
		p++;
	}
	cout << (m == B? p: -1) << '\n';
}

void make_updown()
{
	up.clear();
	Mat m = I;
	Loop (i,0,mod) {
		m *= A;
		up.insert({mypair(m.up()), i+1});
	}
	Ap = m;
}

ll find(const better_map<ll> &small, pll target)
{
	ll p = 0;
	Mat mi = I;
	Mat Api = Ap.inv();
	Loop (_,0,mod) {
		// x * m = target
		// x = target * m.inv
		pll cand = target * mi;
		auto it = small.find(mypair(cand));
		if (it != small.end()) {
			debugl(1) {
				cerr << "find//////\n";
				cerr << cand.first << ' ' << cand.second << '\n';
				cerr << "*\n";
				auto m = mi.inv();
				cerr << m[0] << ' ' << m[1] << '\n';
				cerr << m[1] << ' ' << m[2] << '\n';
				cerr << "=\n";
				cerr << target.first << ' ' << target.second << '\n';
				cerr << "//////////\n";
			}
			return p + it->second;
		}
		mi *= Api;
		p += mod;
	}
	return -1;
}

Mat pw(Mat x, ll y) {
	Mat a = I;
	while (y) {
		if (y%2)
			a *= x;
		x *= x;
		y /= 2;
	}
	return a;
}

void solve()
{
	cin >> mod;
	Loop (i,0,4)
		cin >> A[i];
	Loop (i,0,4)
		cin >> B[i];

	if (A == B) {
		cout << "1\n";
		return;
	}
	if (B == I) {
		cout << "0\n";
		return;
	}
	if (A == Mat{}) {
		cout << "-1\n";
		return;
	}
	if (!A.det()) {
		return solve_det0();
	}

	make_updown();
	ll l1 = find(up  , {1, 0});
	ll p1 = find(up  , B.up  ());
	debug {
		cerr << "a % " << l1 << " = " << p1 << '\n';
		//cerr << "a % " << l2 << " = " << p2 << '\n';
	}
	if (p1 == -1) {
		cout << "-1\n";
		return;
	}

	ll ans = p1 % l1;
	auto m = pw(A, ans);
	if (m != B) {
		cout << "-1\n";
		return;
	}

	debug {
		cerr << "debug///\n";
		cerr << m[0] << ' ' << m[1] << '\n';
		cerr << m[2] << ' ' << m[3] << '\n';
		if (m != B)
			cerr << "ERROR!!!!!!!!!!!!!!!!!!!\n";
		cerr << "////////\n";
	}

	cout << ans << '\n';
}

signed main()
{
	cin.tie(0) -> sync_with_stdio(false);
	int t = 1;
	cin >> t;
	while (t--)
		solve();
}
0