在刷Leetcode的过程中遇到多次大数操作需要1000000007取模,防止大数越界
大数越界: 随着 nn 增大, f(n)f(n) 会超过 Int32 甚至 Int64 的取值范围,导致最终的返回值错误
就很好奇去搜索了一下原因,搜到最多的答案如下:
为什么要对1000000007取模大数阶乘,大数的排列组合等,一般都要求将输出结果对1000000007取模 为什么总是1000000007呢
= =大概≖‿≖✧是因为:(我猜的,不服你打我呀~)
- 1000000007是一个质数
- int32位的最大值为2147483647,所以对于int32位来说1000000007足够大
- int64位的最大值为2^63-1,对于1000000007来说它的平方不会在int64中溢出 所以在大数相乘的时候,因为(a∗b)%c=((a%c)∗(b%c))%c,所以相乘时两边都对1000000007取模,再保存在int64里面不会溢出
但是对于上述答案,还不能够完全的解答我的疑惑
- 1000000007是一个质数
质数有很多个,选择这个的理由呢?
- int32位的最大值为2147483647,所以对于int32位来说1000000007足够大
在1000000007到2147483647之间还有很多比它要更大的数,足够大并不少最大,并不能说明它的唯一性
- int64位的最大值为2^63-1,对于1000000007来说它的平方不会在int64中溢出 所以在大数相乘的时候,因为(a∗b)%c=((a%c)∗(b%c))%c,所以相乘时两边都对1000000007取模,再保存在int64里面不会溢出
在1000000007到2^62-1之间的数都不会溢出,为何偏偏要选1000000007呢?
如果有哪位大神知道原因,烦请告知,不胜感激!
网友评论