如何找到模数为100000007的大数的多重化
我们知道1000000007是一个大素数。 如何找到模数为1000000007的两个大数的乘法
例如，如果我想找到78627765 * 67527574 mod 1000000007，我该怎么办呢。
至少如果有人告诉我我会尝试的程序
注意：请告诉我原始数据类型的解决方案，如int，long或long long，提前感谢
Modulo链接使用合理的数字来推动数值comp空间的限制：
(A * B) % C == ((A % C) * (B % C)) % C. 这方面的证据非常简单，世界各地的密码学网站上都有成千上万的例子。 一个简单的样本：
（7 * 8）％5 = 56％5 = 1
和
((7 % 5) * (8 % 5)) % 5 = (2 * 3) % 5 = 6 % 5 = 1
我希望这有帮助。 很明显，当A和B已经被推到你的顶级平台极限并且仍然小于C时，它变得毫无意义，但是当不是这种情况时它会非常方便（即当A> C和/或B> C时）。
由于这看起来像家庭作业或背景问题，我只会给出提示。
如果你知道x％m和y％m，你怎么能找到（x + y）％m？ 如果你知道x％m，你怎么能找到（2x）％m？
既然您想找到（a * b）％m，有没有办法可以分解b，以便您可以使用上述两个提示？
你为什么不想使用64位算术呢？ 当然，这仅适用于被乘数的操作数不超过32位（但也可以修复）。 考虑：
typedef unsigned long long uint64; uint64 m = 1000000007UL; uint64 r = (uint64)a * (uint64)b; r = r % m; // get the residue
人们也可以对其进行优化以避免昂贵的’％’：
double inv = 1.0 / 1000000007UL; // precompute inverse uint64 r = (uint64)a * (uint64)b; uint64 rf = (uint64)floor((double)a * (double)b * inv); // floor(a * b / m) r = r - rf * m; // residue
请注意，第二种方法可能需要一些精确的游戏。 您也可以使用’long double’代替