Codeforces Round #670 (Div. 2) E. Deleting Numbers

Problem - E - Codeforces

問題概要

インタラクティブ問題である。

まず正整数 $n$ が与えられる。ジャッジは $1$ 以上 $n$ 以下の整数 $x$ を持っている。また集合 $s$ があり、初期状態では $s=\lbrace 1, 2, ..., n\rbrace$ である。

以下のクエリを合計 $10000$ 回まで投げることができる。 $x$ の値を特定し、Cクエリで解答せよ。

A $a$ ： $s$ に含まれる $a$ の倍数の個数が返答される。
B $a$ ： $s$ に含まれる $a$ の倍数の個数が返答される。その後、 $s$ に含まれる $a$ の倍数のうち $x$ でないものが $s$ から消去される。 $a \gt 1$ でなければならない。
C $a$ ： $x$ の値は $a$ であると解答する。このクエリは $1$ 回しか発行できない。

制約

$1 \le n \le 10^{5}$

解法

数 $x$ を絞り込んでいく基本方針としては、まずBクエリを投げて集合を変化させます。このとき「もし今までBクエリで投げた値の倍数が全部消えていれば、集合にはこの値が残っているはず」という状態を自分で管理しておきます。そしてAクエリ（Bクエリでも可）を投げて、返ってくる値が自分で管理している値と合わないならば、「これまで投げたBクエリの中に $x$ の約数が存在し、今投げたAクエリの値も $x$ の約数である」ということが分かります。このように情報を得るには「消去を試みる→残っているかチェック」という2段階が必要です。

クエリ数 $10000$ は潤沢に見えますが、実際はほとんどの個数を「素数へのBクエリ」に使わないといけません。なぜなら $x$ が素数である場合、それを識別するためにはその素数そのものについてBクエリを投げる必要があるからです。10万以下の素数は $9592$ 個なので、残り $400$ 回程度しか使えません。

また素数についてのBクエリを投げた後、その結果を確認するAクエリも必要です。再び素数全部についてAクエリを投げ直す余裕はないので、これは必然的に A 1 というクエリでまとめて確認することになります。

そのため素数をいくつかのグループに分けて、「1グループの素数全てについてBクエリを投げる→A 1 でチェック」という処理を繰り返すことにします。冒頭に書いた方法でAクエリの結果を照合し、自分で管理している値と合わないのであれば、このグループの中に $x$ の素因数が存在します。そのためグループ内の素数 $p$ 全てについて改めて A $p$ というクエリを投げて $x$ の素因数かどうかを判定します。