给定四个坐标为整数的点：$A(a, 0), B(b, 0), C(0, c), D(0, d)$，其中$0 < a < b$且$0 < c < d$。

在直线AC上选择另一个坐标为整数的点P，使得三角形ABP、CDP和BDP均相似。

容易证明仅当$a=c$时这三个三角形才可能相似。

因此给定$a=c$，我们需要找到三元组$(a,b,d)$，使得AC上至少存在一个坐标为整数的点P满足三角形ABP、CDP和BDP均相似。

例如，当$(a,b,d)=(2,3,4)$时，点$P(1,1)$就满足上述条件。注意三元组$(2,3,4)$和$(2,4,3)$是不同的，尽管对这两个三元组来说$P(1,1)$都满足要求。

满足$b+d < 100$且能使得点P存在的不同三元组$(a,b,d)$一共有$92$个。

满足$b+d < 100000$且能使得点P存在的不同三元组$(a,b,d)$一共有$320471$个。

满足$b+d < 10^8$且能使得点P存在的不同三元组$(a,b,d)$一共有多少个？

本题难度:

解答

设$AP:PC=\lambda$，则容易验证P点坐标是$a/(1+\lambda), c\lambda/(1+\lambda)$。

显然$\angle DCP=\angle PAB=3\pi /4$，若三个三角形相似，则还有$\angle DPB=3\pi /4$。

此时有两种情况$\angle DPC=\angle BPA$，以及$\angle DPC=\angle ABP\neq\angle BPA$。

先考虑$\angle DPC=\angle BPA$的情况，此时有$\angle DPC=\angle BPA=\angle PDB=\angle PBD=\pi/8$，从而三角都是等腰三角形，且$\angle ODB=\angle OBD=\pi/4$。

因而有$b=d$以及$\lambda=1$，进而可得$b-a=\sqrt 2a/2$，显然b就不能是整数，因此不合要求。

接下来考虑$\angle DPC=\angle ABP\neq\angle BPA$的情况，此时有 $$\frac{BA}{PC}=\frac{AP}{CD}=\frac{BP}{PD},$$ 其中第一个等号可推得 $$(b-a)(d-a)=\frac{2\lambda a^2}{(1+\lambda)^2}.$$ 再考虑三角形DPB，它与三角形PAB相似的情况有两种， $$\frac{PB}{PD}=\frac{AB}{AP}, \quad \text{或} \quad \frac{PB}{PD}=\frac{AP}{AB},$$ 联立可知前者推得PC=AP，即$\lambda=1$，后者推得$AB=CD$，即$b=d$。\\ $\lambda=1$时有 $$2(b-a)(d-a)=a^2.$$ 显然此时a是偶数，因此枚举偶平数及其约数即可得到这一情况的所有接。

而$b=d$时则有$(b-a)^2=2\lambda a^2/(1+\lambda)^2$，不难看出$\lambda$需要是有理数，设$\lambda=u/v$，其中$u,v$是互素的正整数，则有 $$(b-a)^2=\frac{2uv a^2}{(u+v)^2}.$$ 由于$u,v$互素，因此$uv$与$u+v$也互素，从而$u+v$需要是a的约数，且$2uv$需要是完全平方数。

在实现中通过a来枚举$u,v$是很低效的，反之应当考虑能写成$2uv$的（偶）平方数，则需要枚举的$u,v$的与上文$\lambda=1$时需要枚举的约数完全相同，再取$u+v$的倍数作为$a$即可。

最终结果是$549936643$。

注：本题的上界很大，直接用筛法找出约数在空间上是不可取的，以下直接使用Sympy的divisor函数计算约数，也因此代码为Python 3，此外，代码中打印了进度信息。

from sympy import divisors

bound=100000000
n=bound//3
r1=r2=0
for a in range(2,n+1,2):
    for u in divisors(a*a//2):
        v=a*a//u//2
        if (u+v+2*a) < bound:
            r1+=1
        if u <= v and 2*(u+v+a) < bound:
            r2+=1
    if a%1000000==0:print(a//1000000, "million checked")

print(r1+r2)