Problem 151
Paper sheets of standard sizes: an expected-value problem.
Project Euler 151
一开始只有一张A1的纸,每次随机取出一张纸
如果不是A5则按题意切,切完拿走一张A5,其余放回
如果是A5则拿走
除去第一次和最后一次,拿的时候发现只剩一张纸的次数的数学期望是多少

每个状态算一遍就行了
对每一天来说,记录 {各大小纸张的数量,至今为止遇到只剩一张纸的情况的次数} = 出现概率
状态不多,用map就够用了
从第一天开始依次计算下一天的所有状态的出现概率
然后(概率*次数)求和即可

Problem 152
Writing 1/2 as a sum of inverse squares
把1/2表示成许多不同整数的平方的倒数的和
求从2~80这几个整数取数,按上述计算,有多少种方法表示1/2

既然最后要表示成1/2,那么分母中除了2以外的质数因子都要能消除才行
怎么才能消除呢…
1/a+1/b=(a+b)/(a*b)
如果a和b互质的话,(a+b)和(a*b)也互质
c/a+d/b=(b*c+a*d)/(a*b)
如果a和b互质且c/a和d/b是既约分数的话,(b*c+a*d)和(a*b)也互质…

因此为了消除分母上的某个质因子,这个质因子至少要在两项中出现
分母只能取2~80的平方,超过40的质数最多只有一个…所以这些数就不考虑了
而超过7的质数之间又是不相关的(2~80中没有哪个数是两个超过7的质数的积)
既然是不相关的就可以单独拿出来看看…能有哪几种消除该质数因子的方法

写段程序检测下来发现含有大于7的质数的因子的数中只有这么一组可以消除该质数的:

	1/144=1/169+1/1521+1/2704=1/132+1/392+1/522

那么还剩下39个数:

2,3,4,5,6,7,8,9,10,12,14,15,16,18,20,21,24,25,27,28,
30,32,35,36,40,42,45,48,49,50,54,56,60,63,64,70,72,75,80

算上1/144这个,还剩40个数,其中12出现2次

既然这结果这么好,那么带7这个因子的数也拿来组合一下试试…
这下就有好多种消除质因子7的组合了,有19个
剩下的数字有30个:

2,3,4,5,6,8,9,10,12,15,16,18,20,24,25,27,
30,32,36,40,45,48,50,54,60,64,72,75,80,12

本来以为这19个组合里面如果两两没有交集的话,还要考虑选取这2个的情况
实际上多虑了,因为两个都选取的情况已经包含在这些组合里面了

那么在这19个数任取一个或者一个都不取…然后和带有5的因子的数组合起来看看消除5这个因子有多少种组合
有475个组合,其中不相同的数有252个
还剩18个数字:
2,3,4,6,8,9,12,16,18,24,27,32,36,48,54,64,72,12

对于3和2的因子也如法炮制,对有重复的数字做个乘法就行了,不要重新算
结果好小…答案正确

Problem 153
Investigating Gaussian Integers
定义高斯整数为实部和虚部都是整数的复数
定义若高斯整数a和高斯整数b满足b/a也是高斯整数,那么称a能整除b
s(n)表示所有能整除n的实部为正的高斯整数的和(即满足n/x是高斯整数的x的和)
求sum{s(n) ,n=1..10^8}

–下面的除法是整数除法
设s(n)=sr(n)+si(n),其中sr(n)表示整数部分的和,si(n)表示虚部不为0的复数部分的和
整数部分的话,很简单

sum{sr(n),n=1..N}=sum{(N/n)*n,n=1..N} 

可以优化一下用O(sqrt(N))的复杂度算出来

不过复数不太好办
设最小的能被a+bi整除的正整数是m(a,b)

m(a,b)/(a+bi)=m(a,b)*(a-bi)/(a2+b2)
因此
m(a,b)=(a2+b2)/gcd(a,b)

于是能被a+bi整除的正整数必须是m(a,b)的倍数
共轭复数是成对出现的,即a+bi可以整除n的话a-bi也可以,而加起来正好是2*a,虚部被抵消了
因此只计算b>0的情况就行了

si(n)=2*sum{a| n%m(a,b)==0, b>0}

分成a=b,a<b和a>b的的情况讨论得到

si(n)=2*sum{a| n%(2*a)==0}+2*sum{a+b| n%m(a,b)==0,a>b>0}

求和后就成了

sum{si(n),n=1..N}=2*sum{(N/(2*a))*a| a=1..N}+2*sum{(N/m(a,b))*(a+b)| 0<b<a≤N}

前半部分和之前算整数部分之和的方法差不多,后半部分怎么办呢
可以开个10^8大的数组,r[i]记录N/i的系数
对每个0<b<a<sqrt(N) ,gcd(a,b)=1的(a,b),给r[(a*a+b*b)*k]+=(a+b)*2*k
相信只有O(N)个这样的项需要处理,gcd复杂度算是O(logN)那么总复杂度是O(N*logN)

感觉内存用的太多,空间复杂度应该可以简化到O(sqrt(N))级别的
r0[1..sqrt(N)]记录N/i的系数
r1[1..sqrt(N)]记录N/k=i的系数

内存消耗不到1MB,耗时20秒
答案正确

Problem 154
Exploring Pascal’s pyramid.
金字塔形堆放的球,顶端的球数字为1,其他球的数字是它上面相邻的3个球的数字之和
也就是每个球上的数字是三项式(x+y+z)ⁿ展开后的系数
问(x+y+z)²⁰⁰⁰⁰⁰ 中有多少个系数是10¹²的整数倍

让人想起Problem 148…不过又是3维又不是质数…
先展开多项式吧
设w=x+y,那么

(x+y+z)n=(w+z)n=sum{C(n,i)*wi*z(n-i)}
	=sum{C(n,i)*(x+y)i*z(n-i)}
	=sum{C(n,i)*C(i,j)*xj*y(i-j)*z(n-i)}

设a=j,b=i-j,c=n-i,分别表示x,y,z的幂次

C(n,i)*C(i,j)=n!*i!/(i!*(n-i)!*j!*(i-j)!)
	=n!/(a!*b!*c!)

要求这个系数是10¹²的整数倍啊…
就是看这个数中2的幂次和5的幂次哪个低咯…低的那个达到12就ok
1~n每个数的阶乘的2的幂次和5的幂次都可以预处理下
枚举a和b,c=n-a-b,复杂度是O(n^2)…虽然不是不能接受…但是不是有点慢…

尝试从小数据中找规律…结果失败了…

那就看看能不能做些常数优化…
设a<=b<=c,减少计算次数
枚举范围是a=[0,n/3],b=[a,(n-a)/2]
那么a,b,c都不相等的时候,n!/(a!*b!*c!)值共出现了6次
a=b或者b=c的时候,出现3次
a=b=c的时候,出现1次

34秒,答案正确

Problem 155
Counting Capacitor Circuits.
设D(n)表示最多用n个相同容量的电容串联并联等能组成多少种不同的电容值
求D(18)

写个处理分数的类…然后暴力
设c(n)表示用n个相同容量的电容可以组成哪些电容值
那么枚举c(i),c(n-1)两两配对进行串联或并联,然后排序去重…
48秒
答案正确