結果

問題 No.3170 [Cherry 7th Tune KY] Even if you could say "See you ..."
ユーザー ymm-knight
提出日時 2025-06-11 14:41:13
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,577 ms / 4,000 ms
コード長 5,627 bytes
コンパイル時間 2,754 ms
コンパイル使用メモリ 232,688 KB
実行使用メモリ 95,508 KB
最終ジャッジ日時 2025-06-11 23:07:08
合計ジャッジ時間 15,744 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

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, down;

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();
	down.clear();
	Mat m = I;
	Loop (i,0,mod) {
		m *= A;
		up  .insert({mypair(m.up  ()), i+1});
		down.insert({mypair(m.down()), 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;
}

vector<ll> coprimes(ll x)
{
	vector<ll> ans;
	for (ll y = 2; y*y <= x; y++) {
		if (x%y)
			continue;
		ll z = 1;
		while (x%y == 0) {
			z *= y;
			x /= y;
		}
		ans.push_back(z);
	}
	if (x)
		ans.push_back(x);
	return ans;
}

pll euc(ll x, ll y)
{
	ll a1 = 1, a2 = 0;
	ll b1 = 0, b2 = 1;
	while (y) {
		ll k = x/y;
		ll z = x - k*y;
		ll c1 = a1 - k*b1;
		ll c2 = a2 - k*b2;
		x = y; y = z;
		a1 = b1; b1 = c1;
		a2 = b2; b2 = c2;
	}
	return {a1, a2};
}

ll inv(ll n, ll m)
{
	auto [x, y] = euc(n, m);
	return (x%m+m)%m;
}

ll chinese_rem(ll m1, ll a1, ll m2, ll a2)
{
	ll g = gcd(m1, m2);
	if (a1 % g != a2 % g)
		return -1;
	ll a3 = a1 % g, m3 = g;
	m1 /= g; a1 %= m1;
	m2 /= g; a2 %= m2;

	vector<pll> vec;
	for (auto m : coprimes(m1))
		vec.push_back({m, a1%m});
	for (auto m : coprimes(m2))
		vec.push_back({m, a2%m});
	for (auto m : coprimes(m3))
		vec.push_back({m, a3%m});

	ll mf = m1*m2*m3;
	ll ans = 0;

	for (auto [m, a] : vec) {
		ll n = inv(mf/m, m);
		debug cerr << a << ' ' << n << ' ' << m << "!\n";
		ans = (ans + (__int128)a * (mf/m) % mf * n) % mf;
	}

	return ans;
}

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 l2 = find(down, {0, 1});
	ll p1 = find(up  , B.up  ());
	ll p2 = find(down, B.down());
	debug {
		cerr << "a % " << l1 << " = " << p1 << '\n';
		cerr << "a % " << l2 << " = " << p2 << '\n';
	}
	if (p1 == -1 || p2 == -1) {
		cout << "-1\n";
		return;
	}
	p1 %= l1;
	p2 %= l2;

	// n % l1 = p1
	// n % l2 = p2
	ll ans = chinese_rem(l1, p1, l2, p2);
	if (ans == -1) {
		cout << "-1\n";
		return;
	}

	debug {
		auto m = pw(A, ans);
		cerr << "debug///\n";
		cerr << m[0] << ' ' << m[1] << '\n';
		cerr << m[2] << ' ' << m[3] << '\n';
		if (m != B)
			cerr << "ERROR!!!!!!!!!!!!!!!!!!!\n";
		cerr << "////////\n";
	}
	debugl(1) {
		cerr << "l1///\n";
		auto m = pw(A, l1);
		cerr << m[0] << ' ' << m[1] << '\n';
		cerr << m[2] << ' ' << m[3] << '\n';
		cerr << "/////\n";
	}

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

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