ハッシング

たとえば文字列のリストやタプルのリストといった要素のコレクションを扱う場合、コレクション内の要素を検索したり、「要素 X はコレクションに含まれているか」といった問い合わせに答えたりするのは、計算コストが非常に高くなります。その一方で、数値の比較は非常に高速であり、コンピュータは（文字列やタプルに比べて）数値の比較を効率的に行えるように最適化されています。したがって、もし対象のデータを数値にマッピングできれば、要素の検索やコレクションへの含有確認などの処理をより迅速に行うことができます。

任意のサイズのデータを固定サイズのデータにマッピングする手法をハッシングと呼びます。このとき得られる数値（ハッシュ）は、元のデータを一意に識別するために使われます。通常、初期データを固定サイズのデータ（数値など）にマッピングできる hash 関数が与えられています。

たとえば Python には組み込みの hash 関数があり、任意の immutable なオブジェクトを数値（通常はの範囲）にマッピングできます。ただし、この関数はイミュータブルなオブジェクトにのみ使用できるため、リストや辞書（いずれも要素を追加・削除できるミュータブルなオブジェクト）をハッシュしようとするとエラーになります:

print(hash(123))               # 123
print(hash('Anna'))            # 2573300035916889866
print(hash('Bob'))             # -2781086332262035333
print(hash((2, 'Simon')))      # -6551767300073204554
print(hash([1, 2]))            # TypeError: unhashable type: 'list'

チャレンジ: 整数のペアをハッシュする

ここではカスタムのハッシュ関数 h を実装してみましょう。これは 2 つの整数を受け取り、そのハッシュ値を返します。関数 h は次のように定義されています:

このようにすることで、ハッシュ値は常に [0; 5077) の範囲内に収まります。

入力

入力の 1 行に、2 つの数値 a と b ($0 \le a, b \le 10^9$) が与えられます。

出力

プログラムは (a, b) のハッシュ値を出力してください。

例

入力	出力
4 5	2916
23452 5432	3751

チャレンジ: 整数のペアをハッシュする

入力

出力

例

Constraints

To check your solution you need to sign in

Sign in to continue