結果

問題 No.2244 Integer Complete
ユーザー lam6er
提出日時 2025-04-16 01:06:46
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,945 bytes
コンパイル時間 279 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 97,276 KB
最終ジャッジ日時 2025-04-16 01:08:15
合計ジャッジ時間 4,701 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read().split()
    ptr = 0
    N, M = int(input[ptr]), int(input[ptr+1])
    ptr += 2
    A = list(map(int, input[ptr:ptr+N]))
    ptr += N
    B = list(map(int, input[ptr:ptr+M]))
    ptr += M

    # Generate x_intervals and y_intervals
    x_intervals = []
    for a in A:
        start = a * a
        end = (a + 1) * (a + 1) - 1
        x_intervals.append((start, end))
    y_intervals = []
    for b in B:
        start = b * b
        end = (b + 1) * (b + 1) - 1
        y_intervals.append((start, end))

    # Check if 1 is covered
    has_A1 = any(a == 1 for a in A)
    has_B1 = any(b == 1 for b in B)
    if not (has_A1 and has_B1):
        print(1)
        return

    # Function to check if a number is in any of the intervals
    def is_in_intervals(x, intervals):
        left = 0
        right = len(intervals) - 1
        while left <= right:
            mid = (left + right) // 2
            start, end = intervals[mid]
            if start > x:
                right = mid - 1
            else:
                if x <= end:
                    return True
                else:
                    left = mid + 1
        return False

    k = 2
    while True:
        divisors = set()
        for i in range(1, int(math.isqrt(k)) + 1):
            if k % i == 0:
                divisors.add(i)
                divisors.add(k // i)
        covered = False
        for d in divisors:
            # Check d in x and k/d in y
            if is_in_intervals(d, x_intervals) and is_in_intervals(k // d, y_intervals):
                covered = True
                break
            # Check d in y and k/d in x
            if is_in_intervals(d, y_intervals) and is_in_intervals(k // d, x_intervals):
                covered = True
                break
        if not covered:
            print(k)
            return
        k += 1

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