这个方法执行半个小时都出不来结果
时间: 2023-10-26 15:31:44 浏览: 30
是的,这个方法的计算量确实非常大,需要消耗大量的时间和计算资源。如果你需要更快的方法来计算 S 的末尾 9 位数字,可以考虑使用数论中的技巧来简化问题。
具体来说,我们可以注意到 S 的每一项都是一个阶乘,而这些阶乘中大部分都包含因子 5 和因子 2,因此我们可以使用数论中的技巧来计算它们的贡献。具体来说,我们可以将每个阶乘分解成 5 和 2 的幂次方的乘积,然后计算它们对 S 的贡献。具体来说,对于每个阶乘 i,我们可以将其分解成如下的形式:
i! = (2^x * 3^y * 5^z * ...)
其中 x 表示 i! 中因子 2 的幂次,y 表示 i! 中因子 3 的幂次,z 表示 i! 中因子 5 的幂次,以此类推。注意到 S 中只需要取后 9 位数字,因此我们只需要计算每个阶乘对后 9 位数字的贡献即可。
具体来说,对于每个阶乘 i,它对 S 的贡献可以表示为:
i! % 10^9 = ((2^x % 10^9) * (3^y % 10^9) * (5^z % 10^9) * ...) % 10^9
其中 % 表示取模运算。由于 10^9 是一个比较小的数,我们可以使用指数同余定理来计算每个因子的幂次。具体来说,对于一个质数 p 和一个整数 a,我们可以使用费马小定理来计算 a 的模 p 意义下的逆元 a^-1,从而计算 a 的任意幂次。具体来说,a 的模 p 意义下的逆元 a^-1 可以表示为:
a^(p-2) % p
因此,我们可以预处理出所有在模 10^9 意义下的 2、3、5、7、11、13、17、19 的逆元,然后在计算每个阶乘的贡献时使用它们来计算每个因子的幂次,从而计算出 i 对 S 的贡献。
以下是一段 Java 代码,可以使用这个方法来计算 S 的末尾 9 位数字:
```
public class Main {
static final int mod = 1000000000;
static final int[] primes = {2, 3, 5, 7, 11, 13, 17, 19};
static final int[] inv = {500000004, 333333336, 200000002, 142857144,
90909092, 76923078, 58823530, 52631580};
public static void main(String[] args) {
long sum = 0;
for (long i = 1; i <= 202320232023L; i++) {
int x = countFactor(i, 2);
int y = countFactor(i, 3);
int z = countFactor(i, 5);
int w = countFactor(i, 7);
int t = countFactor(i, 11);
int q = countFactor(i, 13);
int r = countFactor(i, 17);
int s = countFactor(i, 19);
long prod = powMod(2, x) * powMod(3, y) % mod
* powMod(5, z) % mod * powMod(7, w) % mod
* powMod(11, t) % mod * powMod(13, q) % mod
* powMod(17, r) % mod * powMod(19, s) % mod;
sum += prod;
sum %= mod;
}
System.out.println(sum);
}
static int countFactor(long n, int p) {
int count = 0;
while (n > 0) {
count += n / p;
n /= p;
}
return count;
}
static int powMod(int a, int b) {
int res = 1;
while (b > 0) {
if ((b & 1) == 1) {
res = (int)((long)res * a % mod);
}
a = (int)((long)a * a % mod);
b >>= 1;
}
return res;
}
}
```
这段代码中,我们首先定义了一个 `primes` 数组和一个 `inv` 数组,分别表示模 10^9 意义下的质数和它们的逆元。然后,对于每个阶乘 i,我们首先计算它在模 2、3、5、7、11、13、17、19 意义下的因子的幂次,然后使用指数同余定理和预处理的逆元计算每个因子的贡献,最后将它们乘起来求和即可。注意到在计算每个因子的贡献时需要进行取模运算,因此我们使用长整型来存储中间结果,以避免数值溢出。