Mag Crypto Contest 001
お疲れ様でした。
FA: shobonvip さん
拡張ユークリッドの互除法を使います。
ACL の inv_mod を使うと一発です。
Python のバージョンのせいで pow(e, -1, (p - 1) * (q - 1)) はできないですね(悲しい)
答えは高々$ (p - 1)(q - 1) - 1 なので、 long long で計算できます。
FA: torisasami さん
答えは $ S に含まれるサイクルの大きさのLCMです。
連結成分は必ずサイクルになるため、連結成分ごとの大きさを UnionFind で求めれば良いです。
$ \mod 10^9 + 7 をしながらLCMを計算したくなりますが、それだと正しく計算できません。
素因数分解して、素因数毎に最大の指数を取る必要があります。
FA: shakayami さん
$ S, T それぞれについて文字間の差分を取って $ S', T' とします。
$ S' から $ T' を線形アルゴリズム(KMP, Z-Algorithm, ローリングハッシュなど)で検索することで答えが求まります。
ローリングハッシュでいけると思っていなかったのでちょっと驚きました。
$ dを全探索してローリングハッシュでもいけてしまったようです。
負けました。