Mod計算

851 ワード
AP試験学習記録30年秋 AP試験学習記録30年秋 テキストリンク

応用情報技術者平成30年秋期 午前問27

自然数を除数とした剰余を返すハッシュ関数がある。値がそれぞれ571，1168，1566である三つのレコードのキー値を入力値としてこのハッシュ関数を施したところ，全てのハッシュ値が衝突した。このとき使用した除数は幾つか。

計算としては、仮に除数が x とすると、
571　Mod　x　＝　1168　Mod　x　＝　1566　Mod　x　ですね。

選択肢で一個ずつで計算したらいいですけど、
ただ計算は面倒ので、下記は、ちょっと計算しやすい方法かなと思います。

仮に　571/x = a あまり Y
1168/x = b あまり Y
とすると、
571=ax+Y
1168=bx+Y
(b-a)x=1168-571=597
b-aはある自然数ですね。なので、597÷選択肢が割り切れるが答えですね。

念のため、1566も上記1168のように計算すると、万全ですね。

参照：
https://www.ap-siken.com/kakomon/30_aki/q27.html