結果

問題 No.2244 Integer Complete
ユーザー lam6er
提出日時 2025-03-31 17:33:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,903 bytes
コンパイル時間 150 ms
コンパイル使用メモリ 82,908 KB
実行使用メモリ 72,512 KB
最終ジャッジ日時 2025-03-31 17:34:26
合計ジャッジ時間 5,476 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 19 TLE * 1 -- * 40
権限があれば一括ダウンロードができます

ソースコード

diff # 

import math

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N, M = int(data[idx]), int(data[idx+1])
    idx +=2
    A = list(map(int, data[idx:idx+N]))
    idx +=N
    B = list(map(int, data[idx:idx+M]))
    
    def check_a(x):
        low = 0
        high = len(A) - 1
        best = -1
        while low <= high:
            mid = (low + high) // 2
            a = A[mid]
            lower = a * a
            if lower <= x:
                best = mid
                low = mid + 1
            else:
                high = mid - 1
        if best == -1:
            return False
        a = A[best]
        upper = (a + 1) * (a + 1) - 1
        return x <= upper
    
    def check_b(y):
        low = 0
        high = len(B) - 1
        best = -1
        while low <= high:
            mid = (low + high) // 2
            b = B[mid]
            lower = b * b
            if lower <= y:
                best = mid
                low = mid + 1
            else:
                high = mid - 1
        if best == -1:
            return False
        b = B[best]
        upper = (b + 1) * (b + 1) - 1
        return y <= upper
    
    k = 1
    while True:
        found = False
        max_d = int(math.isqrt(k))
        divisors = set()
        for d in range(1, max_d + 1):
            if k % d == 0:
                divisors.add(d)
                divisors.add(k // d)
        for d in divisors:
            a_ok = check_a(d)
            if a_ok:
                y = k // d
                if check_b(y):
                    found = True
                    break
            b_ok = check_b(d)
            if b_ok:
                x = k // d
                if check_a(x):
                    found = True
                    break
        if not found:
            print(k)
            return
        k += 1

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