結果
問題 | No.2576 LCM Pattern |
ユーザー |
|
提出日時 | 2024-01-06 18:32:07 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,567 bytes |
コンパイル時間 | 299 ms |
コンパイル使用メモリ | 82,484 KB |
実行使用メモリ | 133,380 KB |
最終ジャッジ日時 | 2024-09-27 19:18:48 |
合計ジャッジ時間 | 4,889 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 10 TLE * 1 -- * 12 |
ソースコード
## https://yukicoder.me/problems/no/2576MOD = 998244353import mathdef calc_gcd(A, B):"""正の整数A, Bの最大公約数を計算する"""a = max(A, B)b = min(A, B)while a % b > 0:c = a % ba = bb = creturn bdef main():N, M = map(int, input().split())# Mの約数列挙sqrt_m = int(math.sqrt(M))divisors = []for p in range(1, sqrt_m + 1):if M % p == 0:q = M // pdivisors.append(p)if q != p:divisors.append(q)divisors.sort()lcm_map = {}for d1 in divisors:for d2 in divisors:gcd = calc_gcd(d1, d2)lcm_map[(d1, d2)] = (d1 // gcd) * d2def solve(map1, map2, divisors):new_map = {}for d1 in divisors:for d2 in divisors:lcm = lcm_map[(d1, d2)]if M % lcm != 0:breakif d1 not in map1 or d2 not in map2:continueif lcm not in new_map:new_map[lcm] = 0new_map[lcm] += (map1[d1] * map2[d2]) % MODnew_map[lcm] %= MODreturn new_mapanswer_map = {1:1}base_map = {d: 1 for d in divisors}while N > 0:if N % 2 == 1:answer_map = solve(answer_map, base_map, divisors)N //= 2base_map = solve(base_map, base_map, divisors)print(answer_map[M])if __name__ == "__main__":main()