http://projecteuler.net/index.php?section=problems&id=169
引用
Define f(0)=1 and f(n) to be the number of different ways n can be expressed as a sum of integer powers of 2 using each power no more than twice.
For example, f(10)=5 since there are five different ways to express 10:
1 + 1 + 8
1 + 1 + 4 + 4
1 + 1 + 2 + 2 + 4
2 + 4 + 4
2 + 8
What is f(10^(25))?
注意到
f(2k+1) = f(k)
f(2k) = f(k) + f(k-1) k >= 1
容易得到,对 n = p*2^m(其中p%2==1,m>=0),有:
f(n) = f(p) + m*f(p-1)
因此
f(n+1) = f(p*2^m+1)
= f(p*2^(m-1))
= f(p) + (m-1)*f(p-1)
从而:
x*f(n)+y*f(n+1) = (mx+(m-1)y)f(p-1)+(x+y)f(p)
因此得到下面的代码:
/**
compute x*f(n)+y*f(n+1) where n%2 == 0
*/
def count(x: BigInt, y: BigInt, n: BigInt): BigInt = {
if(n == 0) return x + y
val m = n.lowestSetBit // n = p*2^m where p%2 == 1
val p = n >> m
count(x*m + y*(m-1),x+y,p-1)
}
引用
scala> count(1,0,(10: BigInt).pow(25))
res1: BigInt = 178653872807
分享到:
相关推荐
ProjectEuler题1-16题代码,直接引入Eclipse就可以用
NULL 博文链接:https://lifethinker.iteye.com/blog/290159
project euler代码库1,已测试通过
solution to problem 5
NULL 博文链接:https://linuke.iteye.com/blog/1056283
NULL 博文链接:https://lampeter123.iteye.com/blog/423036
欧拉计划projecteuler.net
Project Euler solutions in assembler.
projecteuler.net 我对 Project Euler 问题的一些解决方案: :
project euler代码库第二部分(已测试通过
project euler代码库第三部分(已测试通过
project euler代码库第五部分(已测试通过
项目欧拉解决方案该存储库包含我对 Project Euler (projecteuler.net) 上发现的编程问题的所有答案。 每个解决方案都是用 Java 编写的,旨在从命令行运行。 解决方案文件中将提供指向相关欧拉问题的链接。 某些解决...
Algorithm-hacktoberfest-projecteuler.zip,此repo包含多种语言的projecteuler问题的解决方案。为新来者特别设计,作为黑客节挑战的一部分。,算法是为计算机程序高效、彻底地完成任务而创建的一组详细的准则。
ProjectEulerQuestions projecteuler.net 上问题的解决方案
投影仪Project Euler 问题的解决方案,请参阅地位# 名称秒1 3 和 5 的倍数0.02 甚至斐波那契数列0.03 最大素因数0.94 最大的回文产品0.15 最小倍数2.56 和平方差0.07 第 10001 个素数0.1解决方案8 系列中最大的产品...
ProjectEuler + 我在Java中(仅Java)对HackerRank的解决方案。 有关更多详细信息,请。 相信我,不是一个奇怪的网站。 ##为什么要用Java? 很好的问题。 会的,如果您是在C ++中使用“ unsigned int / long”的,...
project_euler Project Euler 问题的解决方案 ###Problem 1 - 3 和 5 的倍数### 如果我们列出所有 10 以下是 3 或 5 的倍数的自然数,我们得到 3、5、6 和 9。这些倍数的和是 23。求1000 以下所有 3 或 5 的倍数之...
project-euler:多种语言的projecteuler.net问题解决方案
projecteuler.net 问题的解决方案。 你可以用这些来作弊,但你只是在欺骗自己。 关于代码质量的说明 - 我只是想通过问题来寻找答案。 因此,我不会花时间在输入验证上。 一个更有趣的讨论点是我的答案是针对开发...