文档章节

Project Euler Problem 48 - 求大数的模

BlackJoker
 BlackJoker
发布于 2015/10/14 11:08
字数 379
阅读 22
收藏 0

原题: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导致的。

© 著作权归作者所有

共有 人打赏支持
BlackJoker
粉丝 1
博文 17
码字总数 9270
作品 0
深圳
高级程序员
私信 提问
Bad Coder(2011-01-04)

再优美的语言,如果你真的把它当作草稿来用,也还真是可以写出一些自惭形秽的-_-! 依然以奋斗在 Project Euler 界的我为例(这次的热情貌似久了一点)。 Problem 27 我们拿到的只是坐标,并非...

Pope怯懦懦地
2017/12/09
0
0
快速幂取模算法

Cover.jpg 前言 在算法程序设计竞赛中,我们竞赛选手会经常碰到对某个数N进行求大数次幂并对1e9+7取模的运算的题目,一方面求大数次幂是一个时间复杂度很高的运算(容易超时),另一方面对1...

SpiffyEight77
2017/12/08
0
0
数据加密--详解 RSA加密算法 原理与实现

RSA算法简介 RSA是最流行的非对称加密算法之一。也被称为公钥加密。它是由罗纳德·李维斯特(Ron Rivest)、阿迪·萨莫尔(Adi Shamir)和伦纳德·阿德曼(Leonard Adleman)在1977年一起提出...

IDreamo
08/10
0
0
Bryce1010 Acm模板

目录 STL标准模板库 STL简介 STL pair STL set STL vector STL string STL stack STL queue STL map upperbound和lowerbound STL bitset STL iterator简介 STL algorithm greater< int>()和l......

Fire_to_cheat_
2017/09/20
0
0
微分方程数值分析基础:Euler法

微分方程数值分析基础:Euler法 Euler法作为数值分析的一种方法,主要解决微分方程在求出精确公式没有必要,求不到或者非常困难情况下有用。为数值分析提供了一种渐变的分析手段,但是也要看...

zhangphil
01/05
0
0

没有更多内容

加载失败,请刷新页面

加载更多

手写一个重试机制程序(使用Callable)

java.util.concurrent.Callable<V>接口可以实现多线程,同时还能实现一个简易重试机制。 查看Callable接口源码可知,它内部的call()方法带返回值,同时抛出了异常。 public interface Cal...

哥本哈根的小哥
17分钟前
0
0
能否通过反射修改被 final 修饰的成员变量?

一、背景 日常磨刀 二、阅前须知知识点: 当final修饰的成员变量在定义的时候初始化值,反射就不能动态修改它的值了。 当final修饰的成员变量在定义的时候没有初始化值,就还能通过反射来动态...

jack__0023
36分钟前
0
0
方之熙博士被任命为RISC-V基金会中国顾问委员会主席,加速RISC-V ISA在中国的应用

中国顾问委员会将就RISC-V基金会的教育和应用推广战略提供指导 今天在中国乌镇举行的世界互联网大会(World Internet Conference)上,RISC-V基金会(RISC-V Foundation)宣布,半导体行业资深人...

whoisliang
49分钟前
1
0
为了用户体验,不要做浏览器兼容

读者看到这篇文章的标题也许会感到奇怪,按照通常的经验来说,为了用户体验应该做浏览器兼容,以便让不同的浏览器用户都能有好的体验,从而增加网站的流量,但是我认为做浏览器兼容属于同样的...

Bob2100
50分钟前
1
0
分布式定时任务架构 (二) xxl-job二次开发实践

4个月前,公司有任务调度的需求,需要一周内完成,时间非常紧。 需求有三点: web界面编辑cron表达式,启动,停止任务 接入公司的rpc成本较低,公司有自研的rpc,研发人员希望共用同一套注解 ...

勇哥和你一起学技术
今天
1
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部