結果
問題 |
No.990 N×Mマス計算(Kの倍数)
|
ユーザー |
![]() |
提出日時 | 2025-04-15 22:54:51 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,931 ms / 2,000 ms |
コード長 | 1,639 bytes |
コンパイル時間 | 226 ms |
コンパイル使用メモリ | 81,784 KB |
実行使用メモリ | 99,904 KB |
最終ジャッジ日時 | 2025-04-15 22:56:38 |
合計ジャッジ時間 | 6,661 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 19 |
ソースコード
import sys import math from collections import defaultdict, Counter def main(): N, M, K = map(int, sys.stdin.readline().split()) op_line = sys.stdin.readline().split() op = op_line[0] B = list(map(int, op_line[1:1+M])) A = [int(sys.stdin.readline()) for _ in range(N)] if op == '+': # Handle addition case B_mod = [b % K for b in B] cnt = Counter(B_mod) total = 0 for a in A: a_mod = a % K req = (-a_mod) % K total += cnt.get(req, 0) print(total) else: # Handle multiplication case B_mod = [b % K for b in B] cnt_b = Counter(B_mod) # Function to get all divisors of K 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 list(divisors) divisors_list = get_divisors(K) # Precompute divisor counts divisor_counts = defaultdict(int) for s in divisors_list: divisor_counts[s] = 0 for x, count in cnt_b.items(): g = math.gcd(x, K) for s in divisors_list: if g % s == 0: divisor_counts[s] += count # Calculate total total = 0 for a in A: a_mod = a % K d = math.gcd(a_mod, K) s = K // d total += divisor_counts.get(s, 0) print(total) if __name__ == "__main__": main()