N^2 公式的快速取模

Question

我有一个问题，当我试图解决这个方程时，

( 1*1 + 2*2 + ... + n*n ) % 10234573

我在 C++ 中的解决方案，

#include <iostream>
#include <cmath>

using namespace std;
int main()
{
    unsigned long long int n, s= 0;
    cin >> n;
    if (n%10234573 == 0)
    {
        cout << 0;
    }
    else
    {
        cout << n*(n+1)*((2*n+1))/6 % 10234573;
    }
    return 0;
}

我需要一个大于 10^9 + 快速数字的解决方案。

Answer 1

你应该使用模乘法的分配性属性，这样你就不会溢出。

(ab) % p = ((a%p) (b%p)) %p

对于 3 个数字，你得到（使用上面的公式）

(abc) % p = ((ab) c) % p = ((((a%p) (b%p)) %p) (c%p)) %p

因此，与其先对 3 个数字进行乘法运算，然后取模，不如先对每个数字取模，然后相乘，然后在最后再次取模。

Answer 2

为了处理更大的数字问题，我们需要更有效地使用数字10234573。

我们知道对于 mod，我们有：

(m*n) mod x = ((m mod x)*(n mod x)) mod x

在我们的计算中使用上面的公式：

n*(n+1)*((2*n+1))/6 % 10234573

我们需要摆脱 dividing by 6。

我们知道，要将一个数除以6，我们需要将它除以2和3。

所以我们有

unsigned long long int mod = 10234573;

unsigned long long int data[3] = {n, n + 1, 2*n + 1};

bool dividedByTwo = false;
bool dividedByThree = false;

for(int i = 0; i < 3; i++){
    if(data[i] % 2 == 0 && !dividedByTwo){
       data[i]/=2;
       dividedByTwo = true; 
    }
    if(data[i] % 3 == 0 && !dividedByThree){
       data[i]/=3;
       dividedByThree = true; 
    }
}
//Finally, applying mod to our formula
cout<< ((((data[0]%mod)*(data[1]%mod))%mod)*(data[2]%mod))%mod;

N^2 公式的快速取模

Fast Modulo for N^2 formula

c++

formula