gpt4 book ai didi

c - 输出模运算

转载 作者:太空狗 更新时间:2023-10-29 15:30:00 24 4
gpt4 key购买 nike

在假定程序输出非常大的大多数编码竞赛中,通常指示将输出除以 10000007(或在这种情况下为素数)。素数被取的意义是什么因为在很多情况下我发现给出的数字与 100004 相同(即不是质数)..?

最佳答案

使用质数有两个原因。一个原因是整数以素数为模形成了一个数学域。一个领域中的算术以多种方式工作,就像整数算术一样。这使得字段在某些竞赛问题中很有用,否则在某些情况下使用的序列可能会崩溃。某些算术可能会产生零、其他微不足道的结果或比预期更简单的结果,因为涉及的数字发生在模数的一个因子上,导致发生一些减少或消除。

另一个原因是迫使程序员处理特定大小的整数的算术运算。如果使用合数,则可以使用不求助于大整数算术的其他技术。

例如,假设我们想知道 132 对 35 取模,但我们只有一个非常小的处理器,无法处理三位数,因此无法计算 132 = 169.

好吧,35 = 5•7,而 13 与 3 模 5 和 6 模 7 全等。我们可以计算这些留数的平方,而不是计算 13 的平方,这告诉我们 132 等同于 32 = 9 = 4 模 5 和等同于 62 = 36 = 1 模 7。组合这些残差需要一些额外的知识( Extended Euclidean Algorithm )。对于这些特定的数字,我们可以将 5 的余数乘以 21,将 7 的余数乘以 15,得到 4·21+1·15 = 99。减少对 35 的模数得到 29,这就是答案(13 的余数 < sup>2 模 35).

如果模数是素数,则无法绕过算术。质数模数本质上需要对不超过模数平方的数字进行算术运算(或耗时的变通方法),但复合模数允许对较小的数进行算术运算,最多为模数的两倍。

关于c - 输出模运算,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12785742/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com