結果

問題 No.2244 Integer Complete
ユーザー gew1fw
提出日時 2025-06-12 16:18:33
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 2,331 bytes
コンパイル時間 199 ms
コンパイル使用メモリ 82,220 KB
実行使用メモリ 92,688 KB
最終ジャッジ日時 2025-06-12 16:18:46
合計ジャッジ時間 4,986 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def main():
    import bisect

    N, M = map(int, sys.stdin.readline().split())
    A = list(map(int, sys.stdin.readline().split()))
    B = list(map(int, sys.stdin.readline().split()))
    
    # 预处理A的区间列表
    A_intervals = []
    for a in A:
        a_sq = a * a
        next_sq = (a + 1) * (a + 1)
        A_intervals.append((a_sq, next_sq - 1))
    
    # 预处理B的区间列表
    B_intervals = []
    for b in B:
        b_sq = b * b
        next_sq = (b + 1) * (b + 1)
        B_intervals.append((b_sq, next_sq - 1))
    
    # 检查是否A中存在a_i=1，B中存在b_j=1
    a_has_1 = False
    if A[0] == 1:
        a_has_1 = True
    b_has_1 = False
    if B[0] == 1:
        b_has_1 = True
    if not (a_has_1 and b_has_1):
        print(1)
        return
    
    # 函数：判断x是否在A的区间中
    def is_in_A(x):
        if x < A_intervals[0][0]:
            return False
        low = 0
        high = len(A_intervals) - 1
        while low <= high:
            mid = (low + high) // 2
            a, b = A_intervals[mid]
            if x < a:
                high = mid - 1
            elif x > b:
                low = mid + 1
            else:
                return True
        return False
    
    # 函数：判断y是否在B的区间中
    def is_in_B(y):
        if y < B_intervals[0][0]:
            return False
        low = 0
        high = len(B_intervals) - 1
        while low <= high:
            mid = (low + high) // 2
            a, b = B_intervals[mid]
            if y < a:
                high = mid - 1
            elif y > b:
                low = mid + 1
            else:
                return True
        return False
    
    k = 1
    while True:
        found = False
        # 遍历所有可能的因数对
        max_x = int(k ** 0.5) + 1
        for x in range(1, max_x + 1):
            if k % x != 0:
                continue
            y = k // x
            if is_in_A(x) and is_in_B(y):
                found = True
                break
            # 检查另一个因数对
            x2 = y
            y2 = x
            if is_in_A(x2) and is_in_B(y2):
                found = True
                break
        if not found:
            print(k)
            return
        k += 1

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