Project Euler Problem 48 - 求大数的模
Project Euler Problem 48 - 求大数的模
BlackJoker 发表于2年前
Project Euler Problem 48 - 求大数的模
• 发表于 2年前
• 阅读 15
• 收藏 0
• 评论 0

## 暴力法

``````    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)) {
}
String s = S.toString(10);
return s.substring(s.length() - 10, s.length());
}
``````

## 使用幂模运算规则

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

``````    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.mod(m);
String s = S.toString(10);
return s;
}
``````

## 输出

``````9110846700
time consumed : 124 ms
``````

``````9110846700
time consumed : 89 ms
``````

×