文档章节

Project Euler Problem 48 - 求大数的模

BlackJoker
 BlackJoker
发布于 2015/10/14 11:08
字数 379
阅读 21
收藏 0
点赞 0
评论 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

一些数学名词的笔记

算数(arithmatic): 代数(algebra): 初等代数(elementary algebra): 抽象代数(abstract algebra) 几何(geometry) 数论(number thoery) 群(group) 环(ring):一个代数结构,定义了广义化的算...

NealFeng ⋅ 2014/10/16 ⋅ 0

基础算法学习-求组合数

求组合数可能不是在真正编程中经常用到的东西,不过ACM啊,纯数学运算以及HARD-CORE PROGRAMMING还是经常会碰到的。我们用 C(n,r) 来表示组合数,代表从n个不同小球里取出r个小球的取法。 计...

psaux0 ⋅ 2014/03/29 ⋅ 3

快速幂取模算法

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

SpiffyEight77 ⋅ 2017/12/08 ⋅ 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

微分方程数值分析基础:Euler法

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

zhangphil ⋅ 01/05 ⋅ 0

欧拉计划里一道经典算法题

题目是这样的(pj euler 76): 任意一个数字,例如5,可以写成 5=1+1+1+1+1 5=1+1+1+2 5=1+1+3 5=1+4 5=1+2+2 5=2+3 一共是六种写法(不重复),那么100又多少种写法? 此题不同于高中的排列...

psaux0 ⋅ 2014/04/01 ⋅ 2

欧拉函数(Euler Function)

Cover 欧拉函数 在数论,对正整数n,欧拉函数是小于n的正整数中与n互质的数的数目(φ(1)=1)。此函数以其首名研究者欧拉命名(Euler'so totient function),它又称为Euler's totient function、...

SpiffyEight77 ⋅ 2017/07/25 ⋅ 0

51nod 1024 矩阵中不重复的元素

1024 矩阵中不重复的元素 Project Euler 难度:2级算法题 收藏 关注 一个m*n的矩阵。 该矩阵的第一列是a^b,(a+1)^b,.....(a + n - 1)^b 第二列是a^(b+1),(a+1)^(b+1),.....(a + n - 1)^(b+1...

Fire_to_cheat_ ⋅ 02/23 ⋅ 0

php aes和rsa加密的区别

RSA 非对称加密,公钥加密,私钥解密,反之亦然。由于需要大数的乘幂求模等算法,运行速度慢,不易于硬件实现。 通常私钥长度有512bit,1024bit,2048bit,4096bit,长度越长,越安全,但是生...

High_Mountain ⋅ 2017/11/22 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

Android JNI 读写Bitmap的方法

Java层创建Bitmap,通过JNI将Bitmap传到C/C++进行处理 Java部分 public static native boolean greenBitmap(Bitmap bitmap); C/C++部分 JNIEXPORT jboolean JNICALL Java_com_test_Test_gree......

国仔饼 ⋅ 4分钟前 ⋅ 0

一次性让你懂async/await,解决回调地狱

什么是async? 欢迎留言讨论 async 函数是 Generator 函数的语法糖。使用 关键字 async 来表示,在函数内部使用 await 来表示异步。相较于 Generator,async 函数的改进在于下面四点: 内置执...

阿K1225 ⋅ 4分钟前 ⋅ 0

angular常用命令

.下载更新操作 1.利用npm下载angular的命令行工具AngularCLI: npm install -g @angular/cli 2.下载jquery: npm install --save jquery 3.更新npm: npm i -g npm 4.更新angular: ng update ......

消散了的诗意 ⋅ 6分钟前 ⋅ 0

window.print 页面打印

定义和用法 print() 方法用于打印当前窗口的内容。 语法 window.print(); window.print() 实际上,是浏览器打印功能菜单的一种程序调用。与点击打印功能菜单一样,不能精确分页,不能设置纸型...

初学者的优化 ⋅ 7分钟前 ⋅ 0

魔兽世界 7.0版本上 PVE装备全攻略

  T套 因为大家应该都会打穿副本的所以具体是哪个boss我就不说了。   T1: 所有套装都在【熔火之心】出   T2: 头原来是在【奥妮克希亚的巢穴】改到黑翼之巢的奈法利安了,腿是在【熔火之...

wangchen1999 ⋅ 7分钟前 ⋅ 0

java.math.BigDecimal使用小结

原文地址 java.math.BigDecimal使用小结 divide方法 使用BigDecimal.divide方法时一定要考虑: 除数是否为0 商是否是无限小数 正确的使用方式 判断除数是否为0,是0做另外的处理逻辑 调用除法...

666B ⋅ 10分钟前 ⋅ 0

关于qstring转char乱码问题。

if (OpenClipboard(NULL)) { HGLOBAL hgClip; EmptyClipboard(); QByteArray byay = FValue.toLocal8Bit(); //转latin编码 char *bochsrc_line = byay.data(); hgClip = GlobalAlloc(GMEM_DD......

backtrackx ⋅ 11分钟前 ⋅ 0

了解SSH加密和连接过程

介绍 SSH或安全shell是安全协议,也是安全管理远程服务器的最常用方式。通过使用多种加密技术,SSH提供了一种机制,用于在双方之间建立加密安全连接,对彼此进行身份验证,以及来回传递命令和...

吴伟祥 ⋅ 17分钟前 ⋅ 0

微信小程序

小程序的基础配置:导航栏和tabbar 在app.json文件中配置导航栏和tabrbar 导航栏的设置 设置导航,背景黑色,文字白色,文字内容 { "pages":[ "pages/index/index", "pages/logs/l...

上官清偌 ⋅ 20分钟前 ⋅ 0

【转】百度坐标坐标系之间的转换(JS版代码)

/** * Created by Wandergis on 2015/7/8. * 提供了百度坐标(BD09)、国测局坐标(火星坐标,GCJ02)、和WGS84坐标系之间的转换 *///定义一些常量var x_PI = 3.1415926535897932...

HAVENT ⋅ 22分钟前 ⋅ 0

没有更多内容

加载失败,请刷新页面

加载更多

下一页

返回顶部
顶部