历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

为什么要对1000000007取模？？？

作者：

2010 , 2022-05-21 19:12:43 , 所有人可见 , 阅读 556

为什么要对1000000007取模（取余）

$\color{GoldEnrod}{大数阶乘，大数的排列组合等，一般都要求将输出结果对1000000007取模（取余）}$

也许你会问：

$\color{Coral}{为什么总是1000000007呢？？？}$

大概≖‿≖✧是因为：

1. 1000000007是一个质数（素数），对质数取余能最大程度避免冲突～

2. int32位的最大值为2147483647，所以对于int32位来说1000000007足够大

3. int64位的最大值为2^63-1，对于1000000007来说它的平方不会在int64中溢出

所以在大数相乘的时候，因为`(a∗b)%c=((a%c)∗(b%c))%c`，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出

$\color{MediumTurquoise}{｡◕‿◕｡}$

14 评论

gza 2022-05-21 19:57

还有，在fft里面， $10^9+7$ 的原根是3

iwoeix 2022-05-21 20:08

Orz

2010 2022-05-21 20:39

嗯
~~虽然我听不懂~~

没有你哪有我 2022-05-21 21:30 回复了 2010 的评论

哈哈哈，笑死，兄弟虽然这个词用的好

2010 2022-05-21 21:31 回复了没有你哪有我的评论

cup-pyy 2022-05-22 14:41

第一是NTT，第二 $998244353$ 的原根才是 $3$

gza 2022-05-22 14:54 回复了 cup-pyy 的评论

啊啊啊，写错了

2010 2022-05-22 14:55 回复了 gza 的评论

额

gza 2022-05-22 14:57 回复了 2010 的评论

不过好像 $10^9+7$ 的原根也是3把

2010 2022-05-22 14:57 回复了 gza 的评论

~~别问我，我听不懂~~

cup-pyy 2022-05-22 18:27 回复了 gza 的评论

$1e9 + 7$ 原根是 $5$

gza 2022-05-22 20:21 回复了 cup-pyy 的评论

e,谢谢

事事如意 2022-05-21 19:28

长知识了

2010 2022-05-21 19:29

App 内打开