第N個四面體數mod m？

Question

嗨，我卡在我的任務，這部分需要我找到第四個四面體數字mod m。四面體數是所有n個先前三角形數的和，並且由公式（n（n + 1）（n + 2））/ 6表示。鑑於我應該找到數的模，並且第n個三角形數可以超過long long int的大小，我知道是否有方法計算這個或另一種方法來找到第n個四面體數？模數m可以達到100000，所以我不確定帕斯卡的三角形是否能在這裏工作。謝謝。

Answer 1

Modular arithmetic有

(a*b) % m == ((a % m) * (b % m)) % m 

您可以使用等價，讓您的號碼一系列標準整數類型的屬性。但是，當你將總和除以6時應該小心，因爲模分等值不一定適用於分割。你可以通過首先計算一切模6*m來繞過這個，然後以模m爲模。

您的計算必須能夠安全地乘以兩個數字模m。在這裏，你需要最多（6＆middot; 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; 
}