AOJ 0040 （Affine Cipher : アフィン暗号）

【問題】

https://onlinejudge.u-aizu.ac.jp/problems/0040

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0040

【解説】

アフィン暗号を複合する問題。文字\(\gamma\)について、\(F(\gamma) = (\alpha \cdot \gamma + \beta) \bmod 26 \)の処理を行っているため、\(\{\alpha,\beta\}\)を総当たりで試して複合していき、正しく複合されているかを判定すればよい。制約より、\(\alpha\)は1～26のうち、26と互いに素（最大公約数が1）の数、\(\beta\)は0～25である。

複合する式については、 $$ F(\gamma) = (\alpha \cdot \gamma + \beta) \bmod 26 $$ であることから、 $$ \gamma = \frac{F(\gamma) + (26 - \beta)}{\alpha} \bmod 26 $$ となる。なお、modの世界では通常の除算ができないため、\(\alpha\)で割るかわりに\(\alpha\)の逆元（モジュラ逆数）を掛ける必要がある。また、a=0,b=1・・・とするため、入力した文字コードから"a"に該当する文字コードを引き、処理後に"a"に該当する文字コードを足している。

逆元については、他のプログラミングコンテスト等でも多用するため、ライブラリ化しておくと便利。

【コード】