結果

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

ソースコード

diff # 

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()
0