作者utomaya (乌托马雅)
看板puzzle
标题Re: [中译] ProjectEuler 311 Biclinic Integral Q …
时间Fri Dec 3 22:58:26 2010
※ 引述《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秒以内
--
※ 发信站: 批踢踢实业坊(ptt.cc)
※ 编辑: utomaya (219.71.70.115), 04/27/2015 08:26:11