結果

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

ソースコード

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] * i[3] - i[1] * i[2]) % b]
	datinv.append((i[3] * x % b, (- i[1] * x) % b, (- i[2] * x) % b, i[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*2 + j] += x[i*2 + k] * y[k*2 + j]
				z[i*2 + j] %= b
	return (z[0], z[1], z[2], z[3])

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