c++ - 我将如何处理计算一个非常大的数字并将其存储为 C++ 中的整数？

Question

对于我的离散结构类，我必须在 C++ 中计算 53^37 (mod 77)。在纸上我知道这相当于 4，但是在尝试自己编写代码并四处搜索之后，我似乎无法让它等于 16 以外的任何值。我假设这是因为 53^37 的数字太大了店铺。

标签： c++discrete-mathematics

Answer 1

从字面上看，我们可以说 53^37 53*53*53*53*... a total of 37 times。我们可以重新安排它，53*53 = 2809然后它会2809*2809*2809*... 18 times * a lone 53在最后产生。然后 find 2809 mod 77 = 37，这意味着对于每个乘法，您都会收到 37 的提醒，我们有 18 次乘法要做，

37 ^ 18 = 16890053810563300749953435929，然后我们乘以孤 53 得到895172851959854939747532104237。

这个数字还是太大了，所以我们重复这个过程，37 ^ 18 = 1369 ^ 9，我们找到1369 mod 77 = 60，那么它就是60 ^ 9 * a lone 53 = 534117888000000000，534117888000000000 mod 77 = 4。这可以对任何初始指数递归地完成。