結果

問題 No.2755 行列の共役類
ユーザー Shirotsume
提出日時 2023-08-07 21:47:41
言語 PyPy3
(7.3.15)
結果
WA  
実行時間 -
コード長 1,110 bytes
コンパイル時間 296 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 78,720 KB
最終ジャッジ日時 2024-11-08 03:13:09
合計ジャッジ時間 23,378 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 18 WA * 37 TLE * 2 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys, time, random
from collections import deque, Counter, defaultdict
input = lambda: sys.stdin.readline().rstrip()
ii = lambda: int(input())
mi = lambda: map(int, input().split())
li = lambda: list(mi())
inf = 2 ** 63 - 1
mod = 998244353
from math import gcd
def inv_gcd(a,b):
    a=a%b
    if a==0:
        return (b,0)
    s=b;t=a
    m0=0;m1=1
    while(t):
        u=s//t
        s-=t*u
        m0-=m1*u
        s,t=t,s
        m0,m1=m1,m0
    if m0<0:
        m0+=b//s
    return (s,m0)
def inv_mod(x,m):
    assert 1<=m
    z=inv_gcd(x,m)
    assert z[0]==1
    return z[1]
B, C = mi()

S = set()

ans = 0
for p1 in range(0, B):
    for p2 in range(0, B):
        if gcd(p1, B) != 1 or p2 % C != 0 or (p1, p2) in S:
            continue
        ans += 1
        if ans > 100:
            print('100+'), exit()
        for r1 in range(0, B):
            for r2 in range(0, B):
                if gcd(r1, B) != 1 or r2 % C != 0:
                    continue
                q1 = p1 % B
                q2 = (-r2 * (p1 * r2 + p2) * inv_mod(r1, B)) % B
                S.add((q1, q2))

print(ans)
0