美文网首页算法
为什么大数操作要对1000000007取模?

为什么大数操作要对1000000007取模?

作者: Erich_Godsen | 来源:发表于2021-03-06 11:02 被阅读0次

在刷Leetcode的过程中遇到多次大数操作需要1000000007取模,防止大数越界

大数越界: 随着 nn 增大, f(n)f(n) 会超过 Int32 甚至 Int64 的取值范围,导致最终的返回值错误

就很好奇去搜索了一下原因,搜到最多的答案如下:

为什么要对1000000007取模大数阶乘,大数的排列组合等,一般都要求将输出结果对1000000007取模 为什么总是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里面不会溢出

但是对于上述答案,还不能够完全的解答我的疑惑

  1. 1000000007是一个质数
    质数有很多个,选择这个的理由呢?
  2. int32位的最大值为2147483647,所以对于int32位来说1000000007足够大
    在1000000007到2147483647之间还有很多比它要更大的数,足够大并不少最大,并不能说明它的唯一性
  3. int64位的最大值为2^63-1,对于1000000007来说它的平方不会在int64中溢出 所以在大数相乘的时候,因为(a∗b)%c=((a%c)∗(b%c))%c,所以相乘时两边都对1000000007取模,再保存在int64里面不会溢出
    在1000000007到2^62-1之间的数都不会溢出,为何偏偏要选1000000007呢?

如果有哪位大神知道原因,烦请告知,不胜感激!

相关文章

  • 为什么大数操作要对1000000007取模?

    在刷Leetcode的过程中遇到多次大数操作需要1000000007取模,防止大数越界 大数越界: 随着 nn 增...

  • 36、数组中逆序对的个数

    为什么要模1000000007 - CSDN博客1000000007 是最小的十位质数。模1000000007,可...

  • hihocoder1239分析

    一、题意分析 给定一个n个数的数列,求其中的前缀斐波那契子串的个数对1000000007取模的值。例如:对于数列a...

  • 基础数论

    大数取模 ll ans=0; for(int i=0; i

  • perl-two(2018-05-26)

    第一二章 一、数字运算操作符 +(加)、-(减)、*(乘)、/(除)、**(乘幂操作符)、%(取余)[也叫取模操作...

  • Python学习笔记1——Python基础

    Python基础 操作符: ** 指数 2**3=8 % 取模、取余数 22%6=6 //...

  • [Flutter] 04-Dart语法二

    一. 运算符 1.1. 除法、整除、取模运算 我们来看一下除法、整除、取模运算 1.2. ??=赋值操作 dart...

  • 位运算应用

    取模 由于偶数的最低位为 0,奇数为 1,所以取模运算可以用位操作来代替。 取整 位掩码 通过定义这些选项,可以用...

  • Dart语法 -- [04 - 运算符]

    1.1. 除法、整除、取模运算 我们来看一下除法、整除、取模运算 1.2. ??=赋值操作 dart有一个很多语言...

  • 条件判断if_else语句

    ①if else 语句 ②操作运算符 12%7 = 5 取模 即取余数 12//5 = 2 地板除,取商 一个等...

网友评论

    本文标题:为什么大数操作要对1000000007取模?

    本文链接:https://www.haomeiwen.com/subject/wamjqltx.html