結果
問題 |
No.990 N×Mマス計算(Kの倍数)
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:52:26 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 362 ms / 2,000 ms |
コード長 | 2,373 bytes |
コンパイル時間 | 181 ms |
コンパイル使用メモリ | 81,716 KB |
実行使用メモリ | 119,600 KB |
最終ジャッジ日時 | 2025-04-15 22:54:49 |
合計ジャッジ時間 | 2,962 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
import sys import math from collections import defaultdict def factorize(n): factors = {} while n % 2 == 0: factors[2] = factors.get(2, 0) + 1 n = n // 2 i = 3 while i * i <= n: while n % i == 0: factors[i] = factors.get(i, 0) + 1 n = n // i i += 2 if n > 2: factors[n] = 1 return factors def generate_divisors(factors): divisors = [1] for p, exp in factors.items(): temp = [] p_powers = [] current_power = 1 for _ in range(exp): current_power *= p p_powers.append(current_power) for d in divisors: for power in p_powers: temp.append(d * power) divisors += temp divisors = list(set(divisors)) divisors.sort() 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 = defaultdict(int) for b in B: rem = b % K freq[rem] +=1 ans = 0 for a in A: rem = a % K target = (K - rem) % K ans += freq.get(target, 0) print(ans) else: if K == 1: print(N * M) return factors = factorize(K) divisors = generate_divisors(factors) if not divisors: print(0) return divisors.sort() sub_divisors = {} for d in divisors: subs = [] for x in divisors: if x > d: break if d % x == 0: subs.append(x) sub_divisors[d] = subs count = defaultdict(int) for b in B: g = math.gcd(b, K) if g not in sub_divisors: continue for s in sub_divisors[g]: count[s] +=1 ans = 0 for a in A: rem = a % K g = math.gcd(rem, K) d = K // g ans += count.get(d, 0) print(ans) if __name__ == '__main__': main()