問題一覧 > 通常問題

No.2244 Integer Complete

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 20
作問者 : shobonvipshobonvip / テスター : noya2noya2 👑 NachiaNachia
0 ProblemId : 9087 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-10 01:22:39

問題文

しょぼん君は、いま「インテジャー・コンプリート」というカードゲームに熱中しています。このカードゲームでは、デッキ $A$ とデッキ $B$ の $2$ つのデッキを用意し、それぞれのデッキにいくつかのカードを入れます。

しょぼん君は デッキ $A$ に $N$ 枚のカード $A_1, A_2, \cdots, A_N$ を入れ、デッキ $B$ に $M$ 枚のカード $B_1, B_2, \cdots, B_M$ を入れました。「インテジャー・コンプリート」では、フィールドに整数を置くことで戦います。整数は次の【行動】をすることでフィールドに置くことができます。

【行動】 デッキ $A$ からカード $A_i ~ (1 \le i \le N)$ と、$A_i^2 \le x \lt (A_i+1)^2$ を満たす整数 $x$ を $1$ つ選ぶ。次に、デッキ $B$ からカード $B_j ~ (1 \le j \le M)$ と、$B_j^2 \le y \lt (B_j+1)^2$ を満たす整数 $y$ を $1$ つ選ぶ。そして、フィールドに $x$ と $y$ の積 $xy$ を置く。

しょぼん君がフィールドに置くことができない最小の正整数を求めてください。

制約

  • 入力はすべて整数
  • $1 \le N, M \le 3 \times 10^4$
  • $1 \le A_1 < A_2 < \cdots < A_N \le 3 \times 10^4$
  • $1 \le B_1 < B_2 < \cdots < B_M \le 3 \times 10^4$

入力

$N$ $M$
$A_1$ $A_2$ $\cdots$ $A_N$ 
$B_1$ $B_2$ $\cdots$ $B_M$

出力

しょぼん君がフィールドに置くことができない最小の正整数を出力してください。

なお、制約下で答えが存在することが示されます。

サンプル

サンプル1
入力
2 1
1 2
1
出力
11

デッキ $A$ から選べる整数は $1, 2, 3, 4, 5, 6, 7, 8$、デッキ $B$ から選べる整数は $1, 2, 3$ です。たとえば正整数 $10$ については、デッキ $A$ から $5$ を選び、デッキ $B$ から $2$ を選ぶことでその積である $10$ をフィールドに置くことができます。

$10$ 以下のすべての正整数はフィールドに置くことができます。しかし、デッキ $A$、デッキ $B$ からどのように整数を選んでも正整数 $11$ をフィールドに置くことができません。よって $11$ を出力します。

サンプル2
入力
1 1
1
2
出力
1

デッキ $A$ から選べる整数は $1, 2, 3$、デッキ $B$ から選べる整数は $4, 5, 6, 7, 8$ です。デッキ $A$、デッキ $B$ からどのように整数を選んでも $1$ をフィールドに置くことはできないので、$1$ を出力します。

サンプル3
入力
2 3
1 2
1 3 4
出力
25

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。