結果

問題 No.2755 行列の共役類
ユーザー shobonvip
提出日時 2024-05-10 22:47:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,617 bytes
コンパイル時間 160 ms
コンパイル使用メモリ 82,292 KB
実行使用メモリ 275,460 KB
最終ジャッジ日時 2024-12-20 06:47:11
合計ジャッジ時間 64,836 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 56 TLE * 10
権限があれば一括ダウンロードができます

ソースコード

diff # 

class UnionFind:
	def __init__(self, n):
		self.n = n
		self.parents = [-1] * n
	
	def find(self, x):
		if self.parents[x] < 0:
			return x
		else:
			self.parents[x] = self.find(self.parents[x])
			return self.parents[x]
	
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x == y:
			return
		if self.parents[x] > self.parents[y]:
			x, y = y, x
		self.parents[x] += self.parents[y]
		self.parents[y] = x

import math
from collections import defaultdict
dat = []
var = defaultdict(int)
b, c = map(int,input().split())
if b == c == 1:
	print(1)
	exit()
for i in range(1, b):
	if math.gcd(i, b) == 1:
		for j in range(b):
			if j % c == 0:
				var[((i, j), (0, 1))] = len(dat)
				dat.append(((i, j), (0, 1)))

# 1/ad-bc ((d, -b), (-c, a))
inv = [0] * b
for i in range(1, b):
	if math.gcd(i, b) == 1:
		for j in range(b):
			if i * j % b == 1:
				inv[i] = j


m = len(dat)
#print(m)

datinv = []

for i in dat:
	#assert (i[0][0] * i[1][1] - i[0][1] * i[1][0]) % b != 0
	x = inv[(i[0][0] * i[1][1] - i[0][1] * i[1][0]) % b]
	datinv.append(((i[1][1] * x % b, (- i[0][1] * x) % b), ((- i[1][0] * x) % b, i[0][0] * x % b)))


def prod(x, y):
	z = [[0, 0], [0, 0]]
	for i in range(2):
		for j in range(2):
			for k in range(2):
				z[i][j] += x[i][k] * y[k][j]
				z[i][j] %= b
	return ((z[0][0], z[0][1]), (z[1][0], z[1][1]))

seen = [0] * m
cnt = 0
for i in range(m):
	if cnt >= 101:
		break
	if seen[i] == 1:
		continue

	cnt += 1
	mat = dat[i]
	for x, y in zip(dat, datinv):
		#print(var[prod(prod(x, mat), y)])
		seen[var[prod(prod(x, mat), y)]] = 1

	
if cnt >= 101:
	print("100+")
else:
	print(cnt)
0