c - 该程序的模算术步骤

我在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);

最佳答案

让我们看一个小例子：

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洒得到处都是的时候，你应该仔细考虑你是否需要它，考虑到John's hint：
将两个n位数字相加可产生最多n+1位的数字，并且
将n位数字乘以m位数字会产生一个结果
最多有n+m个数字。
因此，有些地方你需要使用模量特性，有些地方你肯定不需要，但这是你工作的一部分；）。