请你将结果对1e9+7取模后再返回 |
您所在的位置：网站首页 › 结果对10007取模 › 请你将结果对1e9+7取模后再返回 |
请你将结果对1e9+7取模后再返回
|
来源：【C++ 取模mod易错点】由于答案可能会很大，请你将结果对1e9+7取模后再返回_白马金羁侠少年的博客-CSDN博客 在做算法题时我们经常会遇到这样一句话： 由于答案可能会很大，请你将结果对10^9 + 7取模后再返回 附：为什么很多程序竞赛题目都要求答案对 1e9+7 取模？ 1000000007是一个质数 int32位的最大值为2147483647，所以对于int32位来说1000000007足够大 int64位的最大值为2^63-1，对于1000000007来说它的平方不会在int64中溢出 所以在大数相乘的时候，因为(a∗b)%c=((a%c)∗(b%c))%c，所以相乘时两边都对1000000007取模，再保存在int64里面不会溢出这句话看上去只要对变量取模就可以了，但实际上取模的时机有一定的讲究，比如新手很容易犯一下两个错误 错误1：用max比较很大数据时，先取模取mod的时候，如果题目要求你算最大值，并且说由于答案可能很大，输出结果请对1e9+7取，那你千万不能在max函数更新最大值时就取模，这样很可能会出错 比如：题目过程中有四个数据 2e9+7，1e9+6，1e9+5，1e9+4然后算法中你用max求最大值时，如果先模上1e9+7，那你会得到1e9，1e9+6，1e9+5，1e9+4，并且max函数算出的最大值是1e9+6，可是这四个数的最大值应该是2e9 + 7才对 正确做法：在求max的时候不要先取mod，而是都以long long型数据比大小，最后得到最大值是2e9 + 7，再对它取mod，得到结果是1e9 + 7 例题：1339. 分裂二叉树的最大乘积 错误代码示例 class Solution { public: // 乘积 = 某个节点下所有子节点的和 *（整个树的和 - 某个节点下所有子节点的和） typedef long long LL; LL rmax = 0; LL Total = 0; static const LL mod = 1e9 + 7; // 遍历每个结点，更新最大值 LL TreeSum(TreeNode* root) { if (!root) return 0; LL left = TreeSum(root->left); LL right = TreeSum(root->right); LL subsum = left + right + root->val; // 此处先取模，所以数据很大时会出错 rmax = max(rmax, (Total - subsum) * subsum % mod); return subsum; } int maxProduct(TreeNode* root) { if (!root) return 0; Total = TreeSum(root); rmax = 0; TreeSum(root); return rmax % mod; } };
如果让你算1+2+…+n的值（由于答案可能很大，输出结果请对1e9+7取） n的取值范围是1 ~ 1 0 10000 10^{10000} 1010000 那显然如果你在中间过程中不先取mod，必然会爆数据范围，因为不管是int还是long long甚至是double(最大约 1 0 308 10^{308} 10308)都无法存下这个数据 ... long long res = 0; for(int i = 1; i |
类似题：5752. 子数组最小乘积的最大值【本文地址】
今日新闻 |
推荐新闻 |