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

标题:腾讯云 新注册用户域名抢购1元起>>>   

摘要: 获取大数 1^1 + 2^2 + ... + 1000^1000 的最后10个数字,大数求模

原题: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

所以, (1^1+ 2^2+ ... + 1000^1000) % m = (1^1 % m + 2^2 % m + ... + 1000^1000 % 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
博文 17
码字总数 9270
×
BlackJoker
如果觉得我的文章对您有用,请随意打赏。您的支持将鼓励我继续创作!
* 金额(元)
¥1 ¥5 ¥10 ¥20 其他金额
打赏人
留言
* 支付类型
微信扫码支付
打赏金额:
已支付成功
打赏金额: