<分区>
嗨，我被困在我的任务中，部分要求我找到第 n 个四面体数 mod m。四面体数是前面所有 n 个三角形数的总和，用公式 (n(n+1)(n+2))/6 表示。鉴于我应该找到数字的模数并且第 n 个三角数可以超过 long long int 的大小，我可以知道是否有计算这个或其他方法来找到第 n 个四面体数的方法？模 m 可以达到 100000，所以我不确定帕斯卡三角是否适用于此。谢谢。
<分区>
嗨，我被困在我的任务中，部分要求我找到第 n 个四面体数 mod m。四面体数是前面所有 n 个三角形数的总和，用公式 (n(n+1)(n+2))/6 表示。鉴于我应该找到数字的模数并且第 n 个三角数可以超过 long long int 的大小，我可以知道是否有计算这个或其他方法来找到第 n 个四面体数的方法？模 m 可以达到 100000，所以我不确定帕斯卡三角是否适用于此。谢谢。
最佳答案
Modular arithmetic具有以下属性
(a*b) % m == ((a % m) * (b % m)) % m
您可以使用该等价性将您的数字保持在一系列标准整数类型中。但是，当您将总和除以 6 时应该小心，因为模等价对于除法而言不一定正确。您可以通过先计算所有内容对 6*m 取模，然后对所有内容取模 m 来规避此问题。
您的计算必须能够安全地将两个数字相乘为模 m。在这里，你最多需要 (6 · 100,000)²，它适合 64 位整数，但不适合 32 位整数:
std::uint64_t tetra_mod(std::uint64_t n, std::uint64_t m)
{
std::uint64_t m6 = 6*m;
std::uint64_t n0 = n % m6;
std::uint64_t n1 = (n + 1) % m6;
std::uint64_t n2 = (n + 2) % m6;
return (n0 + n1 + n2) % m6 / 6 % m;
}
关于c++ - 第 N 个四面体数 mod m?，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/41466576/