文章目录
  1. 1. 暴力法
  2. 2. 使用幂模运算规则
  3. 3. 实现PE48
  4. 4. 输出
  5. 5. 小结

Project Euler 48 ,获取大数 1^1 + 2^2 + … + 1000^1000 的最后10个数字

暴力法

用[BigInteger]把这些数进行累加,并不会特别大(内存可hold住),见Java代码:

static String bruteForce(int n) {
BigInteger S = BigInteger.ONE;
BigInteger Max = BigInteger.valueOf(n);
for (BigInteger i = BigInteger.valueOf(2); i.compareTo(Max) < 0; i = i.add(BigInteger.ONE)) {

S = S.add(i.pow(i.intValue()));
}

String s = S.toString(10);
return s.substring(s.length() - 10, s.length());
}

使用幂模运算规则

有幂模运算规则:

(a + b) % p = (a % p + b % p) % p

所以, (11+ 22+ … + 10001000) % m = (11 % m + 22 % m + … + 10001000 % m) % m

用BigInteger实现powerMod方法

public static BigInteger powerMod(BigInteger n, BigInteger p, BigInteger m) {
BigInteger r = n.mod(m);
BigInteger tmp = BigInteger.ONE;
while (p.compareTo(BigInteger.ONE) > 0) {
if ((p.byteValue() & 1) != 0) {// p 是奇数,则
tmp = (tmp.multiply(r)).mod(m);
}
r = r.multiply(r).mod(m);
p = p.divide(BigInteger.valueOf(2L));
}
return r.multiply(tmp).mod(m);
}

实现PE48

    public static void main(String[] args) {// 9110846700
long s = System.nanoTime();
System.out.println(usePowerMod(1000));
// System.err.println(bruteForce(1000));
System.out.println("time consumed : " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - s) + " ms");
}
static String usePowerMod(int n) {
BigInteger N = BigInteger.valueOf(n);
BigInteger S = BigInteger.ZERO;
BigInteger m = BigInteger.valueOf((long) Math.pow(10, 10));
for (BigInteger i = BigInteger.ONE; i.compareTo(N) <= 0; i = i.add(BigInteger.ONE)) {
S = S.add(powerMod(i, i, m));
}
S = S.mod(m);
String s = S.toString(10);
return s;
}

输出

使用幂模运算规则的输出:

9110846700
time consumed : 124 ms

使用暴力法的输出:

9110846700
time consumed : 89 ms

小结

发现暴力法速度更快,原因估计是powerMod(BigInteger,BigInteger,BigInteger)创建了太多的重量级BigInteger导致的。

文章目录
  1. 1. 暴力法
  2. 2. 使用幂模运算规则
  3. 3. 实现PE48
  4. 4. 输出
  5. 5. 小结