文档章节

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
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
数据加密--详解 RSA加密算法 原理与实现

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

IDreamo
08/10
0
0

没有更多内容

加载失败,请刷新页面

加载更多

React 服务器渲染原理解析与实践

网盘下载地址 React 服务器渲染原理解析与实践 本套课程,讲解了React中SSR技术的整个搭建思路及流程,完整的从原理上讲清楚了SSR的概念,重点在于讲解编写SSR框架遇到的各种知识点,以及细节...

qq__2304636824
35分钟前
0
0
Jenkins使用

clean install -Dmaven.test.skip=true

1713716445
44分钟前
0
0
多线程

1. 多线程概念。并发和并行的概念。 多线程指的是一段时间内cpu同时执行多个线程。一个程序至少运行>=1个进程,进程就是运行中的程序,而一个进程至少运行>=1个线程,线程是操作系统能调度的...

鱼想吃肉
今天
1
0
HBase 表修复在线方式和离线方式

一、在线修复 1.1 使用检查命令 $ ./bin/hbase hbck 该命令可完整修复 HBase 元数据信息;存在有错误信息会进行输出; 也可以通过如下命令查看详细信息: $ ./bin/hbase hbck -details 1.2 ...

Ryan-瑞恩
今天
3
0
redis 系列二 -- 常用命令

1.基础命令 info ping quit save dbsize select flushdb flushall 2.键命令 2.1 set 直接赋值 set a a 2.2 get 取值 get a 2.3 exists 是否存在 exists a 2.4 expire 设置剩余时间 秒 expire......

imbiao
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部