Problem 146
Investigating a Prime Pattern
Project Euler 146
找n使其满足n^2+1,n^2+3,n^2+7,n^2+9,n^2+13,n^2+27是连续的质数
最小的正整数n是10
求n<150,000,000中满足上面条件的n的和

首先,n肯定是偶数
而且不能有3,7,13 的因子…
然后…枚举判断试试看
速度好慢…不过这样的数好稀少…一百万中才3个…
10
315410
927070

貌似必须是10的倍数?
如果末尾是2的话,n^2+1的末尾就是5了,不是素数
如果末尾是4的话,n^2+9的末尾就是5了
末尾是6的话,n^2+9的末尾也是5
末尾是8的话,n^2+1的末尾也是5
所以n必须是10的倍数
因此n^2+5,n^2+15,n^2+25都一定是合数了,不用判断他们是否是合数
速度加快了近4倍…

n^2末尾2位是0了…
根据3的倍数的各位和是3的倍数这一点可以知道…n^2各位和必须是3k+1,否则加上末尾的1,3,7,9,13,27的各位和就会是3的倍数了
因此,n^2+11,n^2+17,n^2+23必定能被3整除,不用判断了

跑了1.5小时才出来结果…答案正确
貌似还可以用n对7的余数来进一步减少判断量

Problem 147
Rectangles in cross-hatched grids
a*b的网格,每个单位方格中有对角线
这样的网格中有多少个矩形呢?包括斜过来的
设这个函数是f(a,b)
求sum{f(a,b),a<=47,b<=43},(a,b是正整数)

想DP…可是不好办…因为那个斜的…
首先,f(a,b)=f(b,a)这是肯定的
那么可以想象a*b的网格由a*(b-1)的网格2个,中间重叠了a*(b-2)的部分
f(a,b)=f(a,b-1)*2-f(a,b-2)+g(a,b)
这里的g(a,b)是那些同时占据到2条a*1的那些矩形,这样的矩形数量好算些…吧
增加的平放的矩形很简单,是a*(a+1)/2个
增加的斜放的矩形嘛…设为h(a,b)个
由于每条只有1的宽度,所以应该也不难算
看看有哪些是有可能组成矩形的

下侧的对称

中间2种情况其实是对称的,算作一种
从左到右依次编号(1),(2),(2),(3)
那么看看上侧和下侧的组合的情况:h(a,b)=h_11(a,b)+h_12(a,b)+h_13(a,b)+h_21(a,b)+..+h_33(a,b)

(1)-(1):

    h_11(n,2)=n
    h_11(n,3)=(n-1)*2+(n-2)   (n>=2)
    h_11(n,4)=(n-2)*2+(n-3)*2+(n-2)  (n>=2)
    h_11(n,5)=(n-3)*2+(n-4)*2+(n-3)*2+(n-4)  (n>=4)
    h_11(a,b)=
              {(a*2-(b*2-3))*(b-2)+(a-(b-2))  b is even
              {(a*2-(b*2-3))*(b-1)-(a-(b-1))  b is odd
             =(a*2-b*2+3)*(b-2)+(a-b+2)

(1)-(2), (2)-(1):限制住必须是宽为sqrt(2)/2的矩形了

    h_12(a,b)=h_21(a,b)=h_11_0(a-1,b)=((a-1)-(b-2))*2
        =(a-b+1)*2

(1)-(3), (3)-(1):必须宽超过sqrt(2)/2的矩形,和上面(1)-(2),(2)-(1)那种合并起来看就比较方便

    h_12(a,b)+h_13(a,b)=h_21(a,b)+h_31(a,b)
        =(a-(b-1))*2*(b-1)
        =(a-b+1)*2*(b-1)

(2)-(3), (3)-(2):这个不存在满足的情况
(2)-(2), (3)-(3):这2个也合在一起看比较方便

    h_22(a,b)+h_33(a,b)
    b=4:(a-b)*2+(a-b+1)*2+(a-b)*2+(a-b+1)
    b=5:(a-b)*2+(a-b+1)*2+(a-b)*2+(a-b+1)*2+(a-b)
    h_22(a,b)+h_33(a,b)=(a-b)*b+(a-b+1)*(b-1)

连在一起就是:

h(a,b)=h_11(a,b)+(h_12(a,b)+h_13(a,b))*2+(h_22(a,b)+h_33(a,b))
    =(a*2-b*2+3)*(b-2)+(a-b+2)+(a-b+1)*2*(b-1)*2+(a-b)*b+(a-b+1)*(b-1)
    =8*a*b-8*a-8*b^2+16*b-9
g(a,b)=a*(a+1)/2+8*a*b-8*a-8*b^2+16*b-9

然后就是简单的dp了,答案正确

Problem 148
Exploring Pascal’s triangle.
杨辉三角中前10^9行中不能被7整除的数有多少

杨辉三角中所有数都用它除7的余数来表示的话,就是找不为0的项的个数
设A={
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 3 3 5 1
1 6 1 6 1 6 1
}
也就是模7的杨辉三角前7行,有28个非7倍数的数
那么前14行是
A
A A
中间空余部分倒三角形的区域全是0,也就是是7的倍数
前49行是
B={
A
A A
A 2A A
A 3A 3A A
A 4A 6A 4A A
A 5A 3A 3A 5A A
A 6A 1A 6A 1A 6A A
}
由于7是质数,所以n*A(n<7)不会出现7的倍数
来张图片好理解一些:很像Sierpinski三角形吧

其中灰色的部分是7的倍数

算非7倍数的项很方便:
前7^2行有28^2个非7倍数的项
前7^3行有28^3个非7倍数的项
以此类推

剩下的就简单了,O(logn)的复杂度搞定吧
瞬出,答案正确

Problem 149
Searching for a maximum-sum subsequence.
2000*2000的矩阵(有负数)中找出行、列、对角线方向的连续项之和的最大值

对每整行、整列、整对角线分别做最大子段和
复杂度O(n^2)
不到一秒就出结果,答案正确

Problem 150
Searching a triangular array for a sub-triangle having minimum-sum.
堆成一千行三角形的数字,找一个子三角形,使得其包含的数字之和最小

枚举子三角形的上顶点,然后往下扩展
每行都预处理下,以便快速得到该行的各区间和
O(n^3),隐藏的常系数较小
5秒搞定,答案正确