結果

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

ソースコード

diff # 

import sys
import math

def main():
    input = sys.stdin.read
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    A = list(map(int, data[idx:idx+N]))
    idx += N
    B = list(map(int, data[idx:idx+M]))
    idx += M
    
    x_ranges = []
    for a in A:
        l = a * a
        r = (a + 1) * (a + 1) - 1
        x_ranges.append((l, r))
    
    y_ranges = []
    for b in B:
        l = b * b
        r = (b + 1) * (b + 1) - 1
        y_ranges.append((l, r))
    
    # Check if 1 is present
    has_x1 = any(l <= 1 <= r for (l, r) in x_ranges)
    has_y1 = any(l <= 1 <= r for (l, r) in y_ranges)
    if not (has_x1 and has_y1):
        print(1)
        return
    
    # Precompute y ranges for faster look-up
    y_list = []
    for l, r in y_ranges:
        y_list.append((l, r))
    
    # For each k starting from 2, check if it's present
    k = 2
    while True:
        found = False
        for a in A:
            l = a * a
            r = (a + 1) * (a + 1) - 1
            if l > k:
                break
            
            # Find any x in [l, r] that divides k
            # Get all divisors of k
            divisors = set()
            for i in range(1, int(math.sqrt(k)) + 1):
                if k % i == 0:
                    divisors.add(i)
                    divisors.add(k // i)
            
            for x in divisors:
                if l <= x <= r:
                    y = k // x
                    # Check if y is in any of y_ranges
                    for (yl, yr) in y_list:
                        if yl <= y <= yr:
                            found = True
                            break
                    if found:
                        break
            if found:
                break
        
        if not found:
            print(k)
            return
        
        k += 1

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