DouKaku?

(2^m, p) のペアが解になりやすい理由のかなりいい加減な説明です。

説明中の a1,b1,a2,b2 というグループは #1555 shiroさんのプログラムの
ものです。
 
■ b1グループには偶数はほとんどない。

偶数 x は奇素数 p,q で x = p+q と書けるだろう。（ゴールドバッハ予想）
Aさんに知らされた積が p*q だったら ペアの可能性は (1,p*q) と (p,q) の
２通りしかありえないがたいてい p*q は n を超える（本当？）ので答えは
(p,q) しかありえない。つまりAさんは答えがわかる。
これは Bさんの「Aさんが『分かりません』というのは分かっていました」に
反するので b1グループに x は入らない。

■ 約数がほとんど偶数だと a2グループに入りやすい。

Aさんに知らされた積が x とすると AさんはBさんに知らされた和の候補と
して {a+b| a*b = x} を考える。
x の約数がほとんど偶数だと a も b も偶数の確率が高いので a+b も
ほとんど偶数。よってほとんどの a+b は b1グループに属さず残りの可能性
のあるペア (a,b) を絞り込みやすい。
つまりAさんが「それなら，分かりました」となる確率が高い。

■ (2^m)*p （p は奇素数）は a2グループに入りやすい。

(2^m)*p の約数 {1,2,...,2^m,p,2*p,...(2^m)*p} のほとんどは偶数。
（奇数は 1 と p のみ）
よって (2^m)*p は a2グループに入りやすい。

■ 積が (2^m)*p で、和が b1グループに入るペアはたいてい (2^m, p) のみ。

和の候補 {2^i+(2^(m-i))*p| i <= m} のほとんどは偶数で奇数なのは
1+(2^m)*p と p+2^m の２つのみ。(2^m)*p はたいてい n より大きい（本当？）
ので和の可能性があるのは p+2^m。つまりペアは (2^m, p) 。

［注意]

上記は (2^m, p) 以外が解になりにくいことの説明にはないっていません。
a2 を実際に書かせてみればわかるのですが (2^m)*p 以外の値も結構入って
います。それがなぜ最終的に b2グループで (2^m)*p だけに絞られるのかは
全然わかりません。