JAVA 计算 3^n - 3*2^n + 3 的最优方法。

Question

我正在计算
((3^n) - (3*(2^n)) + 3) 对于 JAVA 中的 1<=N<=109。

但根据问题陈述，看起来需要花费很多时间来计算。

double mul =  Math.pow(3,k);
double mul2 = Math.pow(2,k);    
double res =  ((mul - ((3* mul2)) + 3 ) % (1000000000 + 7));

我面临的问题是

1) Time limit exceeded in java.(which should be less than 1 sec)
2) The result goes out of limit and thus provides wrong output.

任何改进代码/计算方法的建议都会有所帮助。如您所见，要显示的结果是模数 (1000000000 + 7)。 我也尝试编写自己的幂函数，在每次乘法后我都做这个模，这也无济于事。

谢谢

Answer 1

避免使用 BigIntegers 并从头开始评估幂，这是幼稚且低效的方法。

使用模块化算法逐步完成工作。

保留两个整数变量，其值分别为 Aₙ:= 3ⁿ mod 1000000007 和 Bₙ:= 3×2ⁿ mod 1000000007。

更新很明显:Aₙ₊ₗ= 3×Aₙ mod 1000000007 和 Bₙ₊ₗ= 2×Bₙ mod 1000000007。

对于模运算，我建议使用比较而不是 %。

您很幸运，2×1000000007 适合 32 位有符号整数。但不是 3×1000000007，所以我建议将乘以 3 作为两次加法来执行。

因此，您只需实现整数加法和减法模 1000000007。

private static int sum(int x, int y)
{
    return x >= 1000000007 - y ? x - (1000000007 - y) : x + y;
}

private static int sub(int x, int y)
{
    return x < y ? x + (1000000007 - y) : x - y;
}

int n;
int a= 1;
int b= 3;
for (n= 1; n <= 109; n++)
{
    a= sum(sum(a, a), a);
    b= sum(b, b);
    int res= sum(sub(a, b), 3);
}