相似三角形

给定四个坐标为整数的点：

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)

一共有多少个？

本题难度:

解答

设

A P : P C = λ

，则容易验证P点坐标是

a / (1 + λ), c λ / (1 + λ)

。

显然

∠ D C P = ∠ P A B = 3 π / 4

，若三个三角形相似，则还有

∠ D P B = 3 π / 4

。

此时有两种情况

∠ D P C = ∠ B P A

，以及

∠ D P C = ∠ A B P \neq ∠ B P A

。

先考虑

∠ D P C = ∠ B P A

的情况，此时有

∠ D P C = ∠ B P A = ∠ P D B = ∠ P B D = π / 8

，从而三角都是等腰三角形，且

∠ O D B = ∠ O B D = π / 4

。

因而有

b = d

以及

λ = 1

，进而可得

b - a = \sqrt{2} a / 2

，显然b就不能是整数，因此不合要求。

接下来考虑

∠ D P C = ∠ A B P \neq ∠ B P A

的情况，此时有

\frac{B A}{P C} = \frac{A P}{C D} = \frac{B P}{P D},

其中第一个等号可推得

(b - a) (d - a) = \frac{2 λ a^{2}}{(1 + λ)^{2}} .

再考虑三角形DPB，它与三角形PAB相似的情况有两种，

\frac{P B}{P D} = \frac{A B}{A P}, 或 \frac{P B}{P D} = \frac{A P}{A B},

联立可知前者推得PC=AP，即

λ = 1

，后者推得

A B = C D

，即

b = d

。\

λ = 1

时有

2 (b - a) (d - a) = a^{2} .

显然此时a是偶数，因此枚举偶平数及其约数即可得到这一情况的所有接。

而

b = d

时则有

(b - a)^{2} = 2 λ a^{2} / (1 + λ)^{2}

，不难看出

λ

需要是有理数，设

λ = u / v

，其中

u, v

是互素的正整数，则有

(b - a)^{2} = \frac{2 u v a^{2}}{(u + v)^{2}} .

由于

u, v

互素，因此

u v

与

u + v

也互素，从而

u + v

需要是a的约数，且

2 u v

需要是完全平方数。

在实现中通过a来枚举

u, v

是很低效的，反之应当考虑能写成

2 u v

的（偶）平方数，则需要枚举的

u, v

的与上文

λ = 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)