难倒了只有 0 return

Question

好吧，稍微修改一下示例 encode 99 18 108 45 = Nothing 实际上是正确的，显然我无法正确阅读问题，因为 99 和 18 不是素数，所以我在代码中添加了一个检查函数：

coprime :: Int -> Int -> Bool
coprime a b = gcd a b == 1

check :: Int -> Int -> Bool
check p q = (isPrime p) && (isPrime q)

phi :: Int -> Int -> Int
phi p q = (p - 1) * (q - 1)

encrypt :: Int -> Int -> Int -> Int -> Int
encrypt p q m e = powmod m e (p * q)

encode :: Int -> Int -> Int -> Int -> Maybe Int
encode p q m e |check p q && coprime (phi p q) e = Just (encrypt p q m e)
           |otherwise = Nothing

这次我的问题似乎是encode 53 73 151 90 = Just 133 但是这个例子说它应该 return Just 3869 而不是 Just 133。

所以我想问你们的问题是：我只是个白痴，没有看到眼前的错误，还是我的工作正常？

如果您愿意，我也会提供 isPrime 代码，但它只是检查是否为否。是否为质数 return 为真或假。

Answer 1

您的问题是您将数字提高到大次方，这导致非常大数字，并且 Int通常最多包含 64 位数字。结果，我们得到溢出，CPU 将执行回绕。

通常不是计算a^b[=83=的好主意] c直接通过公式计算。我们可以在这里使用更聪明的方法：因为 (a×b) mod c == ((a mod c) × (b mod c)) mod c ，我们可以通过以需要最少内存的方式计算功率来利用此属性：

powmod :: Int -> Int -> Int -> Int
powmod _ 0 _ = 1
powmod a b c | even b = ab2
             | otherwise = mod (a * ab2) c
    where ab2 = powmod (mod (a * a) c) (div b 2) c

所以我们在这里计算 O(log b)（使用 b value幂）a^b mod c，其中 a^b 本身可以通过在所有递归级别执行 modulo 操作变得非常大。我们这里假设c小于Int的最大值的平方根。由于 Int 至少具有 2²⁹-1 的最小上限，这意味着只要 c ≤ 它就可以工作23'170。如果您需要一个适用于更高值的函数，那么您最好使用 Int64（c 的最大值为 3'037'000'499）或 Integer（任意最大值） .

现在我们可以将此函数用于 encrypt 函数：

encrypt :: Int -> Int -> Int -> Int
encrypt p q m e = powmod m e (p * q)

您的 encode 功能还可以改进。您使用 == True，这是不必要的，因为 True == True 是 True，而 False == True 是 False。

encode :: Int -> Int -> Int -> Int -> Maybe Int
encode p q m e | coPrime (phi p q) e = Just (encrypt p q m e)
               |otherwise = Nothing

现在我们得到：

Prelude> encode 99 18 108 45
Just 1134
Prelude> encode 37 17 23 48
Nothing

难倒了只有 0 return

Stumped on Just 0 return

haskell

encode