平成30年度 秋期 午前 問27

✓ これが正解ウ199

解説

三つの差をすべて割り切る199です。

自然数で割った余りを返すハッシュ関数に三つのキー値を入れたところ、ハッシュ値が全て同じになった、という場面から、使った除数を求める問いです。キーの値から格納位置を決めるこの仕組みはハッシングと呼ばれます。手がかりは一つだけで、余りが同じという条件を引き算に言い換えられるかどうかです。ある二つの数を同じ数で割った余りが等しいなら、その二つの差は割り切れます。理由は簡単で、二つの数を除数の倍数と余りの和として書いてから引くと、余りが打ち消し合って除数の倍数だけが残るからです。そこで三つのキー値から差を作ります。1168から571を引くと597、1566から1168を引くと398、1566から571を引くと995です。求める除数は、この三本をすべて割り切る数でなければなりません。素因数に分けると、398は2と199の積、597は3と199の積、995は5と199の積ですから、三本に共通する約数は199だけです。よって除数は199です。検算します。571を199で割ると商が2で余りが173、1168なら商が5で余りが173、1566なら商が7で余りが173となり、三つとも同じ余りになります。見分けの軸は、差を割り切れるかどうかの一点です。選択肢が全て素数で並べられているときは、差を一度素因数分解すれば決まります。

ほかの選択肢はなぜ違うのか

• ア193：193は素数で、398を割り切れません。398は2と199の積なので、約数は1と2と199と398の四つしかなく、193はその中に入りません。差が割り切れない以上、余りをそろえることもできません。
• イ197：197も素数ですが、やはり398の約数ではありません。実際に割ると571は余り177、1168は余り183となり、この時点で二つのハッシュ値がずれるので、三つ全てが同じ値になる条件を満たしません。
• エ211：211で割ると、571は商2で余り149、1168は商5で余り113となり、値が一致しません。211も398の約数ではないため、三つのキー値が同じ位置に集まることはなく、条件に合いません。