結果

問題 No.2755 行列の共役類
ユーザー shobonvipshobonvip
提出日時 2024-05-10 22:50:15
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,572 bytes
コンパイル時間 293 ms
コンパイル使用メモリ 82,168 KB
実行使用メモリ 137,916 KB
最終ジャッジ日時 2024-05-10 22:50:34
合計ジャッジ時間 16,107 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 38 ms
62,316 KB
testcase_01 AC 41 ms
55,212 KB
testcase_02 AC 71 ms
76,704 KB
testcase_03 AC 177 ms
78,300 KB
testcase_04 AC 212 ms
78,612 KB
testcase_05 AC 142 ms
77,336 KB
testcase_06 AC 105 ms
77,320 KB
testcase_07 AC 231 ms
78,352 KB
testcase_08 AC 137 ms
77,340 KB
testcase_09 AC 118 ms
77,556 KB
testcase_10 AC 103 ms
77,388 KB
testcase_11 AC 94 ms
77,300 KB
testcase_12 AC 84 ms
77,060 KB
testcase_13 AC 250 ms
78,836 KB
testcase_14 AC 123 ms
77,264 KB
testcase_15 AC 127 ms
77,244 KB
testcase_16 AC 97 ms
77,132 KB
testcase_17 AC 347 ms
78,912 KB
testcase_18 AC 174 ms
78,212 KB
testcase_19 AC 107 ms
77,176 KB
testcase_20 AC 547 ms
80,756 KB
testcase_21 AC 228 ms
78,784 KB
testcase_22 AC 121 ms
77,788 KB
testcase_23 AC 122 ms
77,564 KB
testcase_24 AC 126 ms
77,352 KB
testcase_25 AC 109 ms
77,208 KB
testcase_26 AC 105 ms
77,208 KB
testcase_27 AC 645 ms
81,860 KB
testcase_28 AC 349 ms
79,044 KB
testcase_29 AC 158 ms
78,552 KB
testcase_30 AC 478 ms
79,624 KB
testcase_31 AC 335 ms
78,884 KB
testcase_32 AC 215 ms
78,880 KB
testcase_33 AC 112 ms
77,412 KB
testcase_34 AC 132 ms
77,368 KB
testcase_35 AC 105 ms
77,504 KB
testcase_36 AC 92 ms
77,276 KB
testcase_37 AC 117 ms
77,152 KB
testcase_38 AC 210 ms
78,620 KB
testcase_39 AC 258 ms
78,624 KB
testcase_40 AC 230 ms
78,380 KB
testcase_41 AC 381 ms
79,180 KB
testcase_42 AC 667 ms
81,600 KB
testcase_43 AC 346 ms
79,084 KB
testcase_44 AC 149 ms
77,488 KB
testcase_45 AC 126 ms
77,660 KB
testcase_46 AC 93 ms
77,264 KB
testcase_47 AC 101 ms
77,452 KB
testcase_48 AC 339 ms
79,132 KB
testcase_49 AC 75 ms
77,160 KB
testcase_50 AC 113 ms
77,448 KB
testcase_51 AC 75 ms
77,328 KB
testcase_52 AC 75 ms
77,316 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] * 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