結果

問題 No.990 N×Mマス計算（Kの倍数）
ユーザー lam6er
提出日時 2025-04-15 22:48:47
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 315 ms / 2,000 ms
コード長 2,279 bytes
コンパイル時間 180 ms
コンパイル使用メモリ 81,860 KB
実行使用メモリ 120,832 KB
最終ジャッジ日時 2025-04-15 22:50:38
合計ジャッジ時間 2,889 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 19
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
from math import gcd
from collections import Counter

def get_divisors(n):
    factors = {}
    temp = n
    i = 2
    while i * i <= temp:
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            factors[i] = cnt
        i += 1
    if temp > 1:
        factors[temp] = 1
    divisors = [1]
    for p in factors:
        exponents = [p**e for e in range(factors[p] + 1)]
        new_divisors = []
        for d in divisors:
            for exp in exponents:
                new_divisors.append(d * exp)
        divisors = list(set(new_divisors))
    divisors = sorted(divisors)
    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_line = input[ptr:ptr + M + 1]
    ptr += M + 1
    op = op_line[0]
    B = list(map(int, op_line[1:M + 1]))

    A = []
    for _ in range(N):
        A.append(int(input[ptr]))
        ptr += 1

    if op == '+':
        freq_b = Counter()
        for b in B:
            mod = b % K
            freq_b[mod] += 1
        total = 0
        for a in A:
            required_mod = (-a) % K
            total += freq_b.get(required_mod, 0)
        print(total)
    else:
        if K == 1:
            print(N * M)
            return
        all_divisors = get_divisors(K)
        divisors_of = {}
        for d in all_divisors:
            temp = []
            for x in all_divisors:
                if x > d:
                    break
                if d % x == 0:
                    temp.append(x)
            divisors_of[d] = temp
        freq_b = Counter()
        for b in B:
            mod = b % K
            freq_b[mod] += 1
        sum_freq = {d: 0 for d in all_divisors}
        for r, cnt in freq_b.items():
            g0 = gcd(r, K)
            if g0 not in divisors_of:
                continue
            for d in divisors_of[g0]:
                sum_freq[d] += cnt
        total = 0
        for a in A:
            x = a % K
            d = gcd(x, K)
            k_prime = K // d
            total += sum_freq.get(k_prime, 0)
        print(total)

if __name__ == "__main__":
    main()
0