結果

問題 No.990 N×Mマス計算(Kの倍数)
ユーザー lam6er
提出日時 2025-03-20 18:47:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,279 bytes
コンパイル時間 146 ms
コンパイル使用メモリ 82,364 KB
実行使用メモリ 116,968 KB
最終ジャッジ日時 2025-03-20 18:48:10
合計ジャッジ時間 7,828 ms
ジャッジサーバーID
(参考情報)
judge5 / judge4
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 17 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff #

import sys
import math

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 sorted(divisors)

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 = [int(input[ptr + i]) for i in range(N)]
    ptr += N

    if op == '+':
        rem_count = {}
        for b in B:
            rem = b % K
            rem_count[rem] = rem_count.get(rem, 0) + 1
        total = 0
        for a in A:
            required_rem = (-a) % K
            total += rem_count.get(required_rem, 0)
        print(total)
    else:
        divisors = get_divisors(K)
        divisors_set = set(divisors)
        count = {d: 0 for d in divisors}
        for b in B:
            d = math.gcd(b, K)
            count[d] += 1
        total = 0
        for a in A:
            d_i = math.gcd(a, K)
            x_i = K // d_i
            cnt = 0
            for d in divisors:
                if d % x_i == 0:
                    cnt += count[d]
            total += cnt
        print(total)

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