Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2010-04-16

剰余とりながら計算するやつ

13:32 | 剰余とりながら計算するやつ - naoya_t@topcoder を含むブックマーク はてなブックマーク - 剰余とりながら計算するやつ - naoya_t@topcoder 剰余とりながら計算するやつ - naoya_t@topcoder のブックマークコメント

cafelier先生のコードからの抜粋

cf. https://topcoder-g-hatena-ne-jp.jag-icpc.org/cafelier/20100416/1271391378

typedef long long LL;

LL M = 1000000007LL; // その時々で。素数でない場合は以下のDIV()が使えないことがある

LL ADD(LL x, LL y) { return (x+y) % M; }
LL SUB(LL x, LL y) { return (x-y+M) % M; }
LL MUL(LL x, LL y) { return x*y % M; }
LL POW(LL x, LL e) { LL v=1; for(; e; x=MUL(x,x), e>>=1) if (e&1) v = MUL(v,x); return v; }
LL DIV(LL x, LL y) { return MUL(x, POW(y, M-2)); }

LL C(LL n, LL k) { LL v=1; for(LL i=1; i<=k; i++) v = DIV(MUL(v, n-i+1),i); return v; }

cafeliercafelier2010/04/16 13:28素数でないと成り立たないです。

m(x)=x%MODVALとして、m(x)とm(y)からm(x/y)を求めたいわけなので
x/y=z ⇔ x=zy ⇒ m(x)=m(z)m(y) ⇒ m(x)m(y)^{MODVAL-2}=m(z)m(y)^{MODVAL-1} ⇒(フェルマーの小定理より)⇒ m(x)m(y)^{MODVAL-2}=m(z)
こんな感じ

cafeliercafelier2010/04/16 13:37素でない場合はそもそも先にmodを取ってしまうと情報が落ちて割り算が不可能になってしまうので、パスカルの三角形か何かで、割り算を回避して式を立てる必要があります。

n4_tn4_t2010/04/16 13:51腑に落ちました。どうもありがとうございます!

トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20100416