ProjectEuler 311 Biclinic Integral Q … - 拼圖

※ 引述《babufong (嗶嗶)》之銘言：
: 311. Biclinic Integral Quadrilaterals
: http://projecteuler.net/index.php?section=problems&id=311
: ABCD是個邊長是整數的凸四面體　其中 1 <= AB < BC < CD < AD
: BD的長度是整數　O是BD的中點　AO的長度是整數
: 當ABCD還擁有 AO = CO <= BO = DO 的條件時
: 我們稱此種ABCD為 Biclinic Integral Quadrilaterals（Biclinic整數四邊形？）
: 例如下圖（有點難畫　請點網頁）
: AB = 19, BC = 29, CD = 37, AD = 43, BD = 48, AO = CO = 23
: 使B(N)為滿足 AB^2 + BC^2 + CD^2 + AD^2 <= N 的Biclinic整數四邊形的數量
: 我們可以確定的是 B(10000) = 49, B(1000000) = 38239
: 求 B(10000000000)是多少？
: ------------------------------------------------------------------------------
: 六點就出了　快十一點才起床Orz
: 翻完正好十一點　解出此題的有8人

看起來很複雜 其實不然

假設 AB=a, AD=b, BC=u, CD=v, AO=CO=m, BD=c, BO=OD=c/2=h
∠AOB=α ∠AOD=π-α

餘弦定理
a^2=(c/2)^2+m^2-c*m*cosα ----(1)
b^2=(c/2)^2+m^2-c*m*cos(π-α)=(c/2)^2+m^2+c*m*cosα -----(2)

(1)+(2) ---> a^2+b^2=c^2/2+2*m^2
2*a^2+2*b^2=c^2+4*m^2

c^2=2*a^2+2*b^2-4*m^2 ----- (3)
a, b, m都是整數，c也是整數(題目給定的條件)，由(3)式推知c必有2的因數
BO=OD=c/2=h, h必為整數

a^2+b^2=2*h^2+2*m^2

對於另一個三角形BCD, 由同樣的方法亦可得出 u^2+v^2=2*h^2+2*m^2

所以a^2+b^2=u^2+v^2=2*h^2+2*m^2

而2*h^2+2*m^2=(m-h)^2+(m+h)^2
所以 a^2+b^2=u^2+v^2=(m-h)^2+(m+h)^2

令a^2+b^2=u^2+v^2=(h-m)^2+(h+m)^2 = k --- (4)
k是偶數(因為k=2*h^2+2*m^2)

且a<u<v<b(題目給定的條件)
再加上2個三角形邊長不等式 h-m<a, h+m>b

h-m<a<u<v<b<h+m
所以k是可以表示成3種以上不同2數平方和的偶數

題目所給的例子是k=2210=19^2+43^2=29^2+37^2=1^2+47^2
(h-m=24-23=1, h+m=23+24=47)



B(N)的定義域是AB^2+BC^2+CD^2+AD^2 <= N
即a^2+b^2+u^2+v^2 <= N
2*k<=N
k<=N/2
所以題目至此變成為「找出所有小於等於N/2能表示成3種以上不同2數平方和的偶數k，
算出其組數。」

以k=2210為例
2210=1^2+47^2
2210=19^2+43^2
2210=23^2+41^2
2210=29^2+37^2

2210一共能表示出4種不同2數平方和
所以{(h-m,h+m),(a,b),(u,v)}的解可以是{(1,47), (19,43),(23, 41)}(第1,2,3組解)
或{(1, 47),(19, 43), (29, 37)}(第1, 2, 4組解)
或{(1, 47),(23, 41), (29, 37)}(第1, 3, 4組解)
或{(19, 43),(23, 41), (29, 37)}(第2, 3, 4組解)

所以2210一共能表示成4種不同2數平方和，而產生了4組解

很顯然的，若偶數k能表示成n種不同2數平方和，且n>=3,
則產生了(n*(n-1)*(n-2)/3!)組解

------------以下是計算機(computer)方法-------------

用計算機的方法很簡單
假設不同兩數為i, j, j>i
i從0開始跑,至sqrt(N/4)，因為k=i^2+j^2<=N/2, i<j, 2^i<i^2+j^2<=N/2, i<sqrt(N/4)
j從i+1開始跑 至i^2+j^2<=N/2的最大j值
對於每一組i, j，在陣列的[i^2+j^2]位置上加1

所有i,j值跑完後，在陣列上搜尋一遍，找出所有陣列儲值3以上的元素，
依(n*(n-1)*(n-2)/3!)公式累加之，即得到答案

我用C跑，大約25秒左右，不過論壇中有人可以跑到10秒以內

--