結果

問題 No.990 N×Mマス計算（Kの倍数）
ユーザー lam6er
提出日時 2025-04-16 15:54:41
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,988 bytes
コンパイル時間 520 ms
コンパイル使用メモリ 81,880 KB
実行使用メモリ 119,936 KB
最終ジャッジ日時 2025-04-16 15:56:58
合計ジャッジ時間 8,257 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from math import gcd
from collections import defaultdict

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 == '+':
        cnt_b = defaultdict(int)
        for b in B:
            mod = b % K
            cnt_b[mod] += 1
        total = 0
        for a in A:
            a_mod = a % K
            required_mod = (K - a_mod) % K
            total += cnt_b.get(required_mod, 0)
        print(total)
    else:
        if K == 1:
            print(N * M)
            return
        temp = K
        factors = {}
        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 = list(set(divisors))
        divisors.append(K)
        divisors = list(set(divisors))
        count_k_prime = defaultdict(int)
        for g in divisors:
            k_prime = K // g
            cnt = 0
            for b in B:
                if b % k_prime == 0:
                    cnt += 1
            count_k_prime[k_prime] = cnt
        total = 0
        for a in A:
            g = math.gcd(a, K)
            k_prime = K // g
            total += count_k_prime.get(k_prime, 0)
        print(total)

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