0

我知道为了让这个函数工作 crtHasSolution 首先必须是真的我很难证明 n 可能是一个解决方案关于如何在haskell中编写或检查它的任何想法或提示？

我知道 N 的条件是它必须大于或等于 0 并且小于 m，这是所有 mod 基数的乘积。

结论出处的注释

crtHasSolution :: [Integer] -> [Integer] -> Bool
crtHasSolution as ms = length as > 0 &&
                       length ms > 0 &&
                       length as == length ms &&
                       all (>=0) as &&
                       all (>=2) ms &&
                       pairwise_coprime ms

-- Is a given number a solution to a CRT problem?
-- usage: crtIsSolution n as ms = ans
-- assures: ans == True, if crtHasSolution as ms == True and n is a solution
--          ans == False, otherwise

crtIsSolution :: Integer -> [Integer] -> [Integer] -> Bool
crtIsSolution n as ms = crtHasSolution as ms &&
                        n >= 0 &&
                        n < m
                        where m =

代码

4

1 回答 1

4

来自维基百科：

很容易检查 的值是否x是一个解：计算x每个[ m_i]的欧几里得除法的余数就足够了。

如果x `mod` m_i /= a_i对于 any i，则x不是解决方案。

这有点家庭作业的味道，所以我不会给你一个计算这个的单线，而是给你一些关于你实现的主要问题crtIsSolution n as ms：

  • n如果ms和as是空的，是一个解决方案吗？
  • 如果你能计算出n `mod` m_0 == a_0和 是否n有解，ms_0你as_0能计算出和是否n有解吗？m_0:ms_0a_0:as_0
于 2017-09-17T03:49:45.963 回答