3

中国剰余定理を解くことができる関数を Haskell で作成する必要があります。次の定義で作成する必要があります。

crt :: [(Integer, Integer)] -> (Integer, Integer)

答えは次のようになります

>crt [(2,7), (0,3), (1,5)]
(51, 105)

私は全体的なアイデアを持っていると思いますが、それを書く知識がありません。私は、crt 関数が再帰的でなければならないことを知っています。タプルのリストを 2 つのリストのタプルに分割するヘルパー関数を作成しました。

crtSplit xs = (map fst xs, product(map snd xs))

この例では、次のようになります。

([2,0,1],105)

私が知る必要があるのは、最初のリストの各要素のリストを作成することだと思います。どうすればこれを始められますか?

4

2 に答える 2

6

中国の剰余定理には、とが互いに素である場合に と を 1 つのモジュラー方程式に還元できるという事実に基づいて、代数解があります。x = r1 % m1x = r2 % m2m1m2

そのためには、剰余逆数とは何か、拡張ユークリッド アルゴリズムを使用して効率的に計算する方法を知る必要があります。

これらのピースを組み合わせると、右折で中国剰余定理を解くことができます:

crt :: (Integral a, Foldable t) => t (a, a) -> (a, a)
crt = foldr go (0, 1)
    where
    go (r1, m1) (r2, m2) = (r `mod` m, m)
        where
        r = r2 + m2 * (r1 - r2) * (m2 `inv` m1)
        m = m2 * m1

    -- Modular Inverse
    a `inv` m = let (_, i, _) = gcd a m in i `mod` m

    -- Extended Euclidean Algorithm
    gcd 0 b = (b, 0, 1)
    gcd a b = (g, t - (b `div` a) * s, s)
        where (g, s, t) = gcd (b `mod` a) a

それから：

\> crt [(2,7), (0,3), (1,5)]
(51,105)
\> crt [(2,3), (3,4), (1,5)]  -- wiki example
(11,60)
于 2016-02-20T21:39:48.640 に答える