結果
問題 |
No.990 N×Mマス計算(Kの倍数)
|
ユーザー |
![]() |
提出日時 | 2025-03-20 18:47:17 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,279 bytes |
コンパイル時間 | 146 ms |
コンパイル使用メモリ | 82,364 KB |
実行使用メモリ | 116,968 KB |
最終ジャッジ日時 | 2025-03-20 18:48:10 |
合計ジャッジ時間 | 7,828 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 17 TLE * 2 |
ソースコード
import sys import math def get_divisors(k): divisors = set() for i in range(1, int(math.isqrt(k)) + 1): if k % i == 0: divisors.add(i) divisors.add(k // i) return sorted(divisors) def main(): input = sys.stdin.read().split() ptr = 0 N, M, K = map(int, input[ptr:ptr+3]) ptr += 3 op = input[ptr] ptr += 1 B = list(map(int, input[ptr:ptr+M])) ptr += M A = [int(input[ptr + i]) for i in range(N)] ptr += N if op == '+': rem_count = {} for b in B: rem = b % K rem_count[rem] = rem_count.get(rem, 0) + 1 total = 0 for a in A: required_rem = (-a) % K total += rem_count.get(required_rem, 0) print(total) else: divisors = get_divisors(K) divisors_set = set(divisors) count = {d: 0 for d in divisors} for b in B: d = math.gcd(b, K) count[d] += 1 total = 0 for a in A: d_i = math.gcd(a, K) x_i = K // d_i cnt = 0 for d in divisors: if d % x_i == 0: cnt += count[d] total += cnt print(total) if __name__ == '__main__': main()