結果

問題 No.2244 Integer Complete
ユーザー gew1fw
提出日時 2025-06-12 21:26:34
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,875 bytes
コンパイル時間 624 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 91,136 KB
最終ジャッジ日時 2025-06-12 21:28:01
合計ジャッジ時間 5,240 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys

def is_in_A(x, A_ranges):
    if not A_ranges:
        return False
    left = 0
    right = len(A_ranges) - 1
    res = -1
    while left <= right:
        mid = (left + right) // 2
        a, b = A_ranges[mid]
        if a <= x:
            res = mid
            left = mid + 1
        else:
            right = mid - 1
    if res == -1:
        return False
    a_val, b_val = A_ranges[res]
    return x < b_val

def is_in_B(y, B_ranges):
    if not B_ranges:
        return False
    left = 0
    right = len(B_ranges) - 1
    res = -1
    while left <= right:
        mid = (left + right) // 2
        c, d = B_ranges[mid]
        if c <= y:
            res = mid
            left = mid + 1
        else:
            right = mid - 1
    if res == -1:
        return False
    c_val, d_val = B_ranges[res]
    return y < d_val

def get_divisors(m):
    divisors = set()
    for i in range(1, int(m**0.5) + 1):
        if m % i == 0:
            divisors.add(i)
            divisors.add(m // i)
    return divisors

def main():
    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_ranges = []
    for a in A:
        a_sq = a * a
        next_a_sq = (a + 1) * (a + 1)
        A_ranges.append((a_sq, next_a_sq))
    
    B_ranges = []
    for b in B:
        b_sq = b * b
        next_b_sq = (b + 1) * (b + 1)
        B_ranges.append((b_sq, next_b_sq))
    
    m = 1
    while True:
        found = False
        divisors = get_divisors(m)
        for x in divisors:
            if is_in_A(x, A_ranges):
                y = m // x
                if is_in_B(y, B_ranges):
                    found = True
                    break
        if not found:
            print(m)
            return
        m += 1

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