結果

問題 No.2755 行列の共役類
ユーザー shobonvipshobonvip
提出日時 2024-05-10 22:47:39
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,617 bytes
コンパイル時間 170 ms
コンパイル使用メモリ 82,384 KB
実行使用メモリ 122,624 KB
最終ジャッジ日時 2024-05-10 22:48:06
合計ジャッジ時間 19,549 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 39 ms
54,516 KB
testcase_01 AC 38 ms
56,112 KB
testcase_02 AC 80 ms
77,072 KB
testcase_03 AC 238 ms
78,204 KB
testcase_04 AC 284 ms
78,448 KB
testcase_05 AC 215 ms
77,748 KB
testcase_06 AC 137 ms
77,716 KB
testcase_07 AC 265 ms
78,660 KB
testcase_08 AC 174 ms
78,044 KB
testcase_09 AC 145 ms
77,904 KB
testcase_10 AC 125 ms
77,928 KB
testcase_11 AC 109 ms
77,312 KB
testcase_12 AC 92 ms
77,248 KB
testcase_13 AC 360 ms
78,600 KB
testcase_14 AC 159 ms
77,632 KB
testcase_15 AC 138 ms
77,928 KB
testcase_16 AC 116 ms
77,852 KB
testcase_17 AC 462 ms
78,900 KB
testcase_18 AC 243 ms
78,360 KB
testcase_19 AC 131 ms
77,848 KB
testcase_20 AC 717 ms
79,964 KB
testcase_21 AC 332 ms
78,644 KB
testcase_22 AC 152 ms
77,908 KB
testcase_23 AC 154 ms
77,760 KB
testcase_24 AC 173 ms
77,772 KB
testcase_25 AC 143 ms
77,832 KB
testcase_26 AC 136 ms
77,860 KB
testcase_27 AC 938 ms
79,956 KB
testcase_28 AC 503 ms
78,696 KB
testcase_29 AC 203 ms
78,508 KB
testcase_30 AC 628 ms
79,624 KB
testcase_31 AC 496 ms
78,712 KB
testcase_32 AC 292 ms
78,376 KB
testcase_33 AC 148 ms
77,972 KB
testcase_34 AC 167 ms
77,668 KB
testcase_35 AC 130 ms
77,804 KB
testcase_36 AC 103 ms
77,096 KB
testcase_37 AC 180 ms
77,876 KB
testcase_38 AC 267 ms
78,508 KB
testcase_39 AC 380 ms
78,568 KB
testcase_40 AC 324 ms
78,400 KB
testcase_41 AC 496 ms
78,700 KB
testcase_42 AC 935 ms
80,028 KB
testcase_43 AC 474 ms
78,844 KB
testcase_44 AC 169 ms
77,804 KB
testcase_45 AC 160 ms
77,780 KB
testcase_46 AC 103 ms
77,132 KB
testcase_47 AC 124 ms
77,576 KB
testcase_48 AC 485 ms
78,376 KB
testcase_49 AC 82 ms
76,976 KB
testcase_50 AC 142 ms
77,720 KB
testcase_51 AC 91 ms
77,088 KB
testcase_52 AC 89 ms
77,332 KB
testcase_53 TLE -
testcase_54 -- -
testcase_55 -- -
testcase_56 -- -
testcase_57 -- -
testcase_58 -- -
testcase_59 -- -
testcase_60 -- -
testcase_61 -- -
testcase_62 -- -
testcase_63 -- -
testcase_64 -- -
testcase_65 -- -
権限があれば一括ダウンロードができます

ソースコード

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