結果
問題 |
No.2755 行列の共役類
|
ユーザー |
![]() |
提出日時 | 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 |
ソースコード
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)