結果

問題 No.990 N×Mマス計算（Kの倍数）
ユーザー lam6er
提出日時 2025-03-31 17:25:08
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,568 bytes
コンパイル時間 198 ms
コンパイル使用メモリ 82,520 KB
実行使用メモリ 122,368 KB
最終ジャッジ日時 2025-03-31 17:25:39
合計ジャッジ時間 9,323 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 17 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import math
from collections import defaultdict

def main():
    input = sys.stdin.read().split()
    ptr = 0
    N, M, K = map(int, input[ptr:ptr+3])
    ptr +=3
    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 == '+':
        modA = defaultdict(int)
        for a in A:
            mod = a % K
            modA[mod] +=1
        
        ans =0
        for b in B:
            mod = b % K
            req = (K - mod) % K
            ans += modA.get(req, 0)
        print(ans)
    else:
        # Calculate divisors of K
        divisors = set()
        k = K
        if k ==0:
            print(0)
            return
        for i in range(1, int(math.isqrt(k)) +1):
            if k % i ==0:
                divisors.add(i)
                divisors.add(k//i)
        divisors = sorted(divisors)
        # Precompute B's divisibility counts
        count_div = defaultdict(int)
        for d in divisors:
            count_div[d] =0
        for b_val in B:
            for d in divisors:
                if d ==0:
                    continue
                if b_val % d ==0:
                    count_div[d] +=1
        ans =0
        for a_val in A:
            g = math.gcd(a_val, K)
            if K ==0:
                xi =0
            else:
                xi = K // g
            # xi must be in divisors of K
            ans += count_div.get(xi, 0)
        print(ans)
    
if __name__ == '__main__':
    main()
0