我有一个任务:
在单元格笔记本(用于数学/数字的标准网格笔记本)上绘制大小为 NxM(整数)的矩形。多少个不同的矩形可以包含这个矩形?
N 和 M 的最大值 == 10^9 (1 000 000 000)
如果结果 >= (10^9 + 7) 显示:结果模 (10^9 + 7)
我知道公式:
M*(M+1) * N*(N+1)/4
并在C++中实现了这个问题:
#include <iostream>
#include <cmath>
#include <iomanip>
int main()
{
long double n, m;
std::cin >> n >> m;
long double n1 = (n*(n + 1) / 2);
long double m1 = (m*(m + 1) / 2);
long double count = std::fmod((n1 * m1), 1000000007);
std::cout << std::fixed << std::setprecision(0) << count;
return 0;
}
但是当我写测试 1000000000 x 1000000000
当 Windows 计算器和 other calculator 时,我的程序显示 499881764显示 441 =_=
我做错了什么?如果有人可以展示正确解决方案的代码示例,我将不胜感激。
最佳答案
您正在失去 long double
类型的精度:您观察到的输出是 2 的幂的倍数这一事实是这种效果的试金石。
因为你使用的是 Windows,我的钱是 long double
作为 64 位 IEEE754 double 浮点类型(即与该平台上的 double
相同) ),这给了你 53 位的精度。
您可以切换到任意精度库,或谷歌“Schranges 算法”以获得计算产品模数的巧妙方法。
关于c++ - 计算和数据限制,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44628870/