結果

問題 No.3170 [Cherry 7th Tune KY] Even if you could say "See you ..."
ユーザー 👑 p-adic
提出日時 2024-03-11 12:26:19
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,677 ms / 4,000 ms
コード長 7,348 bytes
コンパイル時間 440 ms
コンパイル使用メモリ 82,536 KB
実行使用メモリ 79,480 KB
最終ジャッジ日時 2025-06-11 23:05:06
合計ジャッジ時間 25,028 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

class TwoByTwoMatrix:
	zero=None
	one=None

	def __init__(self,M00,M01,M10,M11):
		self.M00 = M00
		self.M01 = M01
		self.M10 = M10
		self.M11 = M11
	def copy(self):
		return self.__class__(self.M00,self.M01,self.M10,self.M11)

	def __eq__(self,other):
		return self.M00 == other.M00 and self.M01 == other.M01 and self.M10 == other.M10 and self.M11 == other.M11
	def __ne__(self,other):
		return not( self == other )

	def __iadd__(self,other):
		self.M00 += other.M00
		self.M01 += other.M01
		self.M10 += other.M10
		self.M11 += other.M11
		return self
	def __add__(self,other):
		M = self.copy()
		M += other
		return M

	def __isub__(self,other):
		self.M00 -= other.M00
		self.M01 -= other.M01
		self.M10 -= other.M10
		self.M11 -= other.M11
		return self
	def __sub__(self,other):
		M = self.copy()
		M -= other
		return M
	def __neg__(self):
		return self.__class__(-self.M00,-self.M01,-self.M10,-self.M11)

	def __mul__(self,other):
		M00 = self.M00 * other.M00 + self.M01 * other.M10
		M01 = self.M00 * other.M01 + self.M01 * other.M11
		M10 = self.M10 * other.M00 + self.M11 * other.M10
		M11 = self.M10 * other.M01 + self.M11 * other.M11
		return self.__class__(M00,M01,M10,M11)
	def __imul__(self,other):
		self = self * other
		return self
	def ScalarMultiply(self,x): #__rmul__にするとx.__class__の__mul__が優先される。
		M00 = x * self.M00
		M01 = x * self.M01
		M10 = x * self.M10
		M11 = x * self.M11
		return self.__class__(M00,M01,M10,M11)

	def det(self):
		return self.M00 * self.M11 - self.M01 * self.M10
	def tr(self):
		return self.M00 + self.M11

	def Adjugate(self):
		M00 = self.M11
		M01 = - self.M01
		M10 = - self.M10
		M11 = self.M00
		return self.__class__(M00,M01,M10,M11)
	def Inverse(self):
		d = self.det()
		return self.Adjugate().ScalarMultiply( 1 / d )
		# assert( d in [1,-1] ) # 整数係数の場合
		# return self.Adjugate().ScalarMultiply( d )
	def __truediv__(self,other):
		return self * other.Inverse()
	def __itruediv__(self,other):
		self *= other.Inverse()
		return self

	def __pow__(self,n):
		if n < 0:n , self = -n , self.Inverse()
		answer = self.__class__.one.copy()
		power = self.copy()
		while n > 0:
			if n&1:answer *= power
			power.Square()
			n >>= 1
		return answer

	#private:
	def Square(self):
		self.M00 , self.M01 , self.M10 , self.M11 = self.M00 ** 2 + self.M01 * self.M10 , ( self.M00 + self.M11 ) * self.M01 , self.M10 * ( self.M00 + self.M11 ) , self.M10 * self.M01 + self.M11 ** 2
TwoByTwoMatrix.zero = TwoByTwoMatrix(0,0,0,0) #ユーザー定義
TwoByTwoMatrix.one = TwoByTwoMatrix(1,0,0,1) #ユーザー定義

class ModB:
	B = 998244353
	length_max = 10**6 #ユーザー定義
	inverse=None
	factorial=None
	factorial_inverse=None
	def SetModulo(B):
		ModB.B = int(B)
		inverse = [None,ModB(1)]
		factorial = [ModB(1)]
		factorial_inverse = [ModB(1)]

	def __init__(self,val,valid = False):
		self.val = int(val)
		if not valid:self.val %= ModB.B
	def copy(self):
		return ModB(self.val,True)

	def __eq__(self,x):
		return x==self.val
	def __ne__(self,other):
		return not( self == other )

	def __add__(self,x):
		val = self.val + x #__radd__を使用
		if val >= ModB.B:val -= ModB.B
		return ModB(val,True)
	def __iadd__(self,other):
		self = self + other
		return self

	def __sub__(self,x):
		val = self.val - x #__rsub__を使用
		if val < 0:val += ModB.B
		return ModB(val,True)
	def __isub__(self,other):
		self = self - other
		return self
	def __neg__(self):
		return ModB(ModB.B - self.val if self.val else 0,True)

	def __mul__(self,x):
		val = self.val * x % ModB.B #__mod__を使用
		return ModB(val,True)
	def __rmul__(self,x):
		return ModB(x * self.val)
	def __imul__(self,x):
		self = self * x
		return self

	def __pow__(self,n):
		if n < 0:n *= Mod.B - 2 #Bが素数でval!=0の場合のみサポート
		answer = ModB(1)
		power = self.copy()
		while n > 0:
			if n&1:answer *= power
			power *= power
			n >>= 1
		return answer

	def Inverse(n): #Bが素数の場合のみサポート
		if n < ModB.length_max:
			while len(ModB.inverse) <= n:ModB.inverse+=[ModB(ModB.B - ModB.inverse[ModB.B % len(ModB.inverse)].val * ( ModB.B // len(ModB.inverse) ) % ModB.B,True)]
			return ModB.inverse[n]
		else:return ModB(n) ** ( ModB.B - 2 )
	def __rtruediv__(self,x):
		return x * ModB.Inverse(self.val)
	def __itruediv__(self,other):
		self *= ModB.Inverse(other.val)
		return self

	def Factorial(n):
		while len(ModB.factorial) <= n:ModB.factorial+=[ModB.factorial[-1] * len(ModB.factorial)]
		return ModB.factorial[n]
	def FactorialInverse(n): #Bが素数の場合のみサポート
		while len(ModB.factorial_inverse) <= n:ModB.factorial_inverse+=[ModB.factorial_inverse[-1] * ModB.Inverse( len(ModB.factorial_inverse) )]
		return ModB.factorial_inverse[n]
	def Combination(n,m): #Bが素数の場合のみサポート
		return ModB.Factorial(n) * ModB.FactorialInverse(m) * ModB.FactorialInverse(n-m)if 0<=m<=n else ModB(0)

	#private:
	def __radd__(self,x): #__add__オーバーロード用
		return x + self.val
	def __rsub__(self,x): #__sub__オーバーロード用
		return x - self.val	
	def __mod__(self,x): #__mul__オーバーロード用
		return self.val
ModB.inverse = [None,ModB(1)]
ModB.factorial = [ModB(1)]
ModB.factorial_inverse = [ModB(1)]

def GCD(a,b):
	c,d=abs(a),abs(b)
	while d:c,d=d,c%d
	return c

def LCM(a,b):
	return a//GCD(a,b)*b if a|b else 0

# gcd(p,q),単位の分割u,v（p*u+q*v=gcd(p,q)）を返す。
def PartitionOfUnity(p,q):
	b,c=[p,q],[[1,0],[0,1]]
	i=p<q
	j=1-i
	while b[j]:
		d=b[i]//b[j]
		c[i][i]-=d*c[j][i]
		c[i][j]-=d*c[j][j]
		b[i]-=d*b[j]
		i,j=j,i
	return b[i],c[i][0],c[i][1]

# gcd(p,q),非負最小解a（a≡s (mod p), a≡t (mod q)）を返す。
# ただし解がない場合はa=-1とする。
def ChineseRemainderTheorem(p,s,q,t):
	g,u,v=PartitionOfUnity(p,q)
	a=-1if s%g!=t%g else(s%g+t//g*p*u+s//g*q*v)%(p*q//g)
	return g,a

I,O,R = input,print,range
J = lambda:map(ModB,I().split())
def Solve():
	P=int(I())
	ModB.SetModulo(P)
	A11,A12 = J()
	A21,A22 = J()
	B11,B12 = J()
	B21,B22 = J()
	A = TwoByTwoMatrix(A11,A12,A21,A22)
	B = TwoByTwoMatrix(B11,B12,B21,B22)
	E = TwoByTwoMatrix(ModB(1),ModB(0),ModB(0),ModB(1))
	TwoByTwoMatrix.one = E.copy()
	if B == E:return O( 0 )
	det_A = A.det()
	det_B = B.det()
	if ( det_A == 0 ) != ( det_B == 0 ):return O( -1 )
	ord_A = -2 if det_A == 0 else -1
	power_A = A.copy()
	for n in R(1,P+1):
		if power_A == B:return O( n )
		if ord_A == -1 and power_A == E:ord_A = n
		power_A *= A
	if ord_A != -1:return O( -1 )
	mod = [ P * ( P - 1 ) , ( P - 1 ) * ( P + 1 ) , P * ( P + 1 ) ]
	A_P = [0]*3
	B_P = [0]*3
	ord_A_P = [-1]*3
	e = [-1]*3
	for i in R(3):
		A_P[i] = A ** mod[i]
		B_P[i] = B ** mod[i]
		power_A = E.copy()
		for n in R(P+2):
			if e[i] == -1 and power_A == B_P[i]:e[i] = n
			if n > 0 and power_A == E:
				ord_A_P[i] = n
				break
			power_A *= A_P[i]
		if e[i] == -1:return O( -1 )
	lcm = LCM( ord_A_P[0] , ord_A_P[1] )
	gcd,x = ChineseRemainderTheorem( ord_A_P[0] , e[0] , ord_A_P[1] , e[1] )
	if x == -1:return O( -1 )
	gcd,x = ChineseRemainderTheorem( lcm , x , ord_A_P[2] , e[2] )
	if x == -1:return O( -1 )
	lcm = LCM( lcm , ord_A_P[2] )
	power_A = A ** x
	A_lcm = A ** lcm
	N = x
	while N <= P * ( P * P - 1 ):
		if power_A == B:return O( N )
		N += lcm
		power_A *= A_lcm
	return O(-1)
for t in R(int(I())):Solve()
0