Hatena::Grouptopcoder

SRM diary(Sigmar)

SigmarのTopcoder SRM参加記録など雑記です。
社会人になってから競技プログラミングを始めました。どこまで行けるか分かりませんが合間を見つけてアルゴリズムの勉強をしています。

2010-07-07SRM475 Div1

余りの出るModの除算

| 23:22 | 余りの出るModの除算 - SRM diary(Sigmar) を含むブックマーク はてなブックマーク - 余りの出るModの除算 - SRM diary(Sigmar) 余りの出るModの除算 - SRM diary(Sigmar) のブックマークコメント

SRM475 Mediumで、整数の世界なら余りの出る除算についてModの世界でどうなるのか色々悩んだので、考えたことを記しておきます。


Modでの除算は、フェルマーの小定理を利用して一意な商が出るように定義されます。

フェルマーの小定理:pが素数でnとpが互いに素のとき、n^(p-1)≡1 (mod p)

フェルマーの小定理によると、n^(p-2) * n ≡ 1 (mod p)なので、nの逆数はn^(p-2)と考えて、m/nをm*(n^(p-2))で計算します。

(通常SRMではpは素数のものが選ばれるよう問題が出されるので、上記の方法で除算が可能)


SRM475 Mediumでは、pは素数なので上記除算が可能です。

この問題文中に、nが奇数のとき、(n+1)/2を計算するという記述が出てきます。

通常のintの演算では、nが奇数のとき(n+1)/2はn/2+1と同じ結果になりますが、Modの世界では同じ結果になりません。

intの世界ではn/mに余りが出るとき、m*(n/m)はnになりません。

一方でModの世界では、フェルマーの小定理を利用した除算は余りが出ない仕組みになっているため、m*(n/m)は必ずnになります。


ということで、答えをmod pで返せという問題では、余りの出る除算はしないこと!

ということが分かりました。間違ってたら教えてください。

トラックバック - http://topcoder.g.hatena.ne.jp/jackpersel/20100707