![解法
MOD p で計算した結果、 X[N]=z になったとする。
1. 0≦z≦2^31-1 になったら z が答。
2. 2^31≦z なら z-p が答。
-2^31 0 2^31 p-2^31 p Z
Z/pZ](https://image.slidesharecdn.com/fourop-120318040726-phpapp02/85/Four-op-6-320.jpg)
![証明
Q[p] = {x in Q ; x = a/b となるような整数 a, b が
存在する。ただし b は p の倍数でない }
このとき、 Q[p] は和や積について閉じている。
( 分母に p を含まない数同士の足し算や掛け算で
新しく分母に p が出てくることはない )
|Y[i]| ≦ 10^6 なので、 X[i] in Q[p] になる。](https://image.slidesharecdn.com/fourop-120318040726-phpapp02/85/Four-op-7-320.jpg)
![証明
f を Q[p] から Z/pZ への写像で、 x = a/b(a,b は整
数、 b は p の倍数でない ) を a*b^(p-2) に写すもの
とする、つまり
f(a/b) = a * b^(p-2)
この関数は well-defined であることが示せる。
つまり x=a/b の表し方は複数あるが、どのように表
したとしても行き先は変わらない。](https://image.slidesharecdn.com/fourop-120318040726-phpapp02/85/Four-op-8-320.jpg)
![証明
この性質を満たすと何が嬉しいのか？
減算や除算は加算や乗算で置き換えて考える。
f(X[N]) = f(X[N-1] op[N] Y[N])
= f(X[N-1]) op[N] f(Y[N])
= f(X[N-2] op[N-1] Y[N-1]) op[N] f(Y[N])
= f(X[N-2]) op[N-1] f(Y[N-1]) op[N] f(Y[N])
…
= f(X[0]) op[1] f(Y[1]) … op[N] f(Y[N])
これで全て MOD p で考えてよいことが示された。](https://image.slidesharecdn.com/fourop-120318040726-phpapp02/85/Four-op-10-320.jpg)
![別解
オンサイト参加された exPacks さんの解法。
オーバーフローしない程度の大きさ (10^8 とか ) の
素数を 2 つ用意する。 (P, Q とおく )
X[N] を mod P, mod Q で計算する。
中国剰余定理で X[N] mod P*Q を計算する。](https://image.slidesharecdn.com/fourop-120318040726-phpapp02/85/Four-op-13-320.jpg)
More Related Content
What's hot (17)
Similar to Four op (20)
![[Basic 14] 暗号について / RSA 暗号 / 楕円曲線暗号](https://cdn.slidesharecdn.com/ss_thumbnails/basic-14-180314083652-thumbnail.jpg?width=560&fit=bounds)
Four op
- 2. 問題概要 数が N(≦10^5) 個与えられるので、足したり引いた り掛けたり割ったりして、最後の値を答えなさい。 ただし計算結果は -2^31 以上 2^31 未満の整数に なることが保証されている。
- 3. ナイーブな解法 Double 型などの浮動小数点数で近似する？ 誤差やオーバーフロー、アンダーフローで WA 。 多倍長整数を用いて有理数の計算を実装する ? 多倍長整数の計算は時間計算量も空間計算量も O(1) ではないので TLE する。
- 4. 着眼点 答えは -2^31 以上 2^31 未満の整数になることが 保証されていることに目をつける。 答えはたかだか 2^32 通りしかない。
- 5. 解法 例えば、 2^32 より大きな素数 p をひとつ固定し て、 MOD p で計算することにしてみよう。 割り算は、 x / y = x * y^(p-2) で計算する ( フェルマーの小定理 ) 。
- 6. 解法 MOD p で計算した結果、 X[N]=z になったとする。 1. 0≦z≦2^31-1 になったら z が答。 2. 2^31≦z なら z-p が答。 -2^31 0 2^31 p-2^31 p Z Z/pZ
- 7. 証明 Q[p] = {x in Q ; x = a/b となるような整数 a, b が 存在する。ただし b は p の倍数でない } このとき、 Q[p] は和や積について閉じている。 ( 分母に p を含まない数同士の足し算や掛け算で 新しく分母に p が出てくることはない ) |Y[i]| ≦ 10^6 なので、 X[i] in Q[p] になる。
- 8. 証明 f を Q[p] から Z/pZ への写像で、 x = a/b(a,b は整 数、 b は p の倍数でない ) を a*b^(p-2) に写すもの とする、つまり f(a/b) = a * b^(p-2) この関数は well-defined であることが示せる。 つまり x=a/b の表し方は複数あるが、どのように表 したとしても行き先は変わらない。
- 9. 証明 写像 f は以下の性質を満たす。 1. f(x + y) = f(x) + f(y) 2. f(x * y) = f(x) * f(y) これは計算することにより簡単に確かめることがで きる。
- 10. 証明 この性質を満たすと何が嬉しいのか？ 減算や除算は加算や乗算で置き換えて考える。 f(X[N]) = f(X[N-1] op[N] Y[N]) = f(X[N-1]) op[N] f(Y[N]) = f(X[N-2] op[N-1] Y[N-1]) op[N] f(Y[N]) = f(X[N-2]) op[N-1] f(Y[N-1]) op[N] f(Y[N]) … = f(X[0]) op[1] f(Y[1]) … op[N] f(Y[N]) これで全て MOD p で考えてよいことが示された。
- 11. 実装上の注意 p は 2^32 より大きい素数である必要があるので、 積をとるときオーバーフローする可能性がある。 オーバーフローを回避しなければならない。 Java で BigInteger を使ってもよい。 意外に早くて十分に間に合う。 modInverse(mod) という便利なメソッドが…
- 12. 実装上の注意 多倍長整数を使わなくてもオーバーフローは回避 できる。 掛け算をバイナリ法で実装しなおす ? → 計算量 O(N* (log p)^2) でやや重い。 通すには定数倍最適化が必要。 p を 10^12 以下にとれば、 M を 10^6 程度にとり、 x * y = ((x * (y / M) % p)*M + x * (y % M)) % p とすることでオーバーフローを回避できる。
- 13. 別解 オンサイト参加された exPacks さんの解法。 オーバーフローしない程度の大きさ (10^8 とか ) の 素数を 2 つ用意する。 (P, Q とおく ) X[N] を mod P, mod Q で計算する。 中国剰余定理で X[N] mod P*Q を計算する。
- 14. 応用例 整数の行列が与えられて行列式を計算したいとき、 掃き出し法を適用するときに除算が楽に実装でき る。 最終的に整数になることが分かっている有理数が 楽に扱えてうれしいことがあるかもしれない。
- 15. 応用問題 ? この問題の input validator を作れ。 つまり、この問題の計算結果がきちんと signed 32bit int の範囲に収まる整数になっているかどうか 確かめよ。 乱択アルゴリズムを用いることにより高い確率で確 かめることができる？ 適当に素数 p をとって計算結果 z が 2^31≦z<p-2^31 となったら棄却できる。 いろんな素数で試せば OK ?
- 16. 解答例 宮村： C++ 60 行 773byte 橋本： Java (BigInteger を使用 ) 29 行 776byte