该程序的模运算步骤

Question

我在 C 中编写了这段代码，其中每个 a,b,cc,ma,mb,mcc,N,k 都是 int 。但是根据问题的说明，N 和 k 可能和 10^9 一样大。 10^9 可以存储在我机器的 int 变量中。但是 a,b,cc,ma,mb,mcc 的内部值和最终值对于 N 和 k 的更大值会更大，即使在 unsigned long long int 变量中也无法存储。

现在，我想打印 mcc % 1000000007 的值，如您在代码中所见。我知道，在 for 循环主体的操作中使用一些巧妙的模运算技巧可以创建正确的输出而不会出现任何溢出，并且还可以提高程序的时间效率。作为模运算的新手，我没能解决这个问题。有人能指出我这些步骤吗？

ma=1;mb=0;mcc=0;
for(i=1; i<=N; ++i){
    a=ma;b=mb;cc=mcc;
    ma = k*a + 1;
    mb = k*b + k*(k-1)*a*a;
    mcc = k*cc + k*(k-1)*a*(3*b+(k-2)*a*a);
}
printf("%d\n",mcc%1000000007);

我的尝试：

我将 a,b,cc,ma,mb,mcc 用作 long long 并完成了此操作。能再优化一下吗？？

ma=1;mb=0;cc=0;
ok = k*(k-1);
for(i=1; i<=N; ++i){
    a=ma;b=mb;
    as = (a*a)%MOD;

    ma = (k*a + 1)%MOD;

    temp1 = (k*b)%MOD;
    temp2 = (as*ok)%MOD;
    mb = (temp1+temp2)%MOD;

    temp1 = (k*cc)%MOD;
    temp2 = (as*(k-2))%MOD;
    temp3 = (3*b)%MOD;
    temp2 = (temp2+temp3)%MOD;
    temp2 = (temp2*a)%MOD;
    temp2 = (ok*temp2)%MOD;
    cc = (temp1 + temp2)%MOD;
}
printf("%lld\n",cc);

Answer 1

我们来看一个小例子：

mb = (k*b + k*(k-1)*a*a)%MOD;

这里，k*b，k*(k-1)*a*a可以溢出，求和也可以，考虑到

(x + y) mod m = (x mod m + y mod m) mod m

我们可以重写这个（x= k*b、y=k*(k-1)*a*a 和 m=MOD）

mb = ((k*b) % MOD + (k*(k-1)*a*a) %MOD) % MOD

现在，我们可以更进一步。自

x * y mod m = (x mod m * y mod m) mod m

我们还可以将乘法 k*(k-1)*a*a % MOD 与 x=k*(k-1) 和 y=a*a 重写为

((k*(k-1)) %MOD) * ((a*a) %MOD)) % MOD

我相信您可以完成剩下的工作。虽然你可以到处撒 % MOD，但你应该仔细考虑是否需要它，将考虑在内：

Adding two n-digit numbers produces a number of up to n+1 digits, and multiplying an n-digit number by an m-digit number produces a result with up to n + m digits.

因此，有些地方您需要使用模数属性，有些地方您肯定不需要，但这是您工作的一部分 ;)。

Answer 2

按照以下思路构建模板 class 是一个很好的练习：

template <int N>
class modulo_int_t
{
public:
    modulo_int_t(int value) : value_(value % N) {}
    modulo_int_t<N> operator+(const modulo_int_t<N> &rhs)
    {
        return modulo_int_t<N>(value_ + rhs.value) ;
    }
    // fill in the other operations
private:
    int value_ ;
} ;

然后使用 modulo_int_t<1000000007> 对象而不是 int 来编写操作。免责声明：在适当的地方使用 long long 并注意负差异...

该程序的模运算步骤

modulo arithmetic steps for this program

c

modulus