結果
問題 |
No.990 N×Mマス計算(Kの倍数)
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:53:55 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 867 ms / 2,000 ms |
コード長 | 2,426 bytes |
コンパイル時間 | 383 ms |
コンパイル使用メモリ | 81,732 KB |
実行使用メモリ | 118,944 KB |
最終ジャッジ日時 | 2025-04-15 22:55:58 |
合計ジャッジ時間 | 3,967 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
import sys import math from collections import defaultdict def factorize(n): factors = [] i = 2 while i * i <= n: if n % i == 0: cnt = 0 while n % i == 0: cnt += 1 n = n // i factors.append((i, cnt)) i += 1 if n > 1: factors.append((n, 1)) return factors def generate_divisors(primes): divisors = [1] for (p, exp) in primes: temp = [] for d in divisors: for e in range(exp + 1): temp.append(d * (p ** e)) divisors = temp return divisors def main(): input = sys.stdin.read().split() ptr = 0 N = int(input[ptr]) ptr += 1 M = int(input[ptr]) ptr += 1 K = int(input[ptr]) ptr += 1 op = input[ptr] ptr += 1 B = list(map(int, input[ptr:ptr+M])) ptr += M A = [] for _ in range(N): A.append(int(input[ptr])) ptr += 1 if op == '+': freq_b = defaultdict(int) for b in B: rem = b % K freq_b[rem] += 1 total = 0 for a in A: rem_a = a % K required_rem = (K - rem_a) % K total += freq_b.get(required_rem, 0) print(total) else: if K == 1: print(N * M) return primes = factorize(K) div_count = defaultdict(int) for b in B: b_mod = b % K g = math.gcd(b_mod, K) g_factors = [] for (p, _) in primes: cnt = 0 temp_g = g while temp_g % p == 0 and temp_g > 0: cnt += 1 temp_g = temp_g // p g_factors.append((p, cnt)) divisors_g = [1] for (p, exp) in g_factors: temp = [] for d in divisors_g: for e in range(exp + 1): temp.append(d * (p ** e)) divisors_g = temp for d in divisors_g: div_count[d] += 1 total = 0 for a in A: a_mod = a % K if a_mod == 0: total += M else: g = math.gcd(a_mod, K) required_divisor = K // g total += div_count.get(required_divisor, 0) print(total) if __name__ == '__main__': main()