Project Euler 299

发表于 更新于 分类于 阅读次数： 本文字数： 3.8k 阅读时长 ≈ 3 分钟

Project Euler 299

题目

Three similar triangles

Four points with integer coordinates are selected:\(A(a,0), B(b,0), C(0,c)\) and \(D(0,d),\) with \(0<a<b\) and \(0<c<d\).

Point \(P\), also with integer coordinates, is chosen on the line \(AC\) so that the three triangles \(ABP, CDP\) and \(BDP\) are all similar.

It is easy to prove that the three triangles can be similar, only if \(a=c\).

So, given that \(a=c\), we are looking for triplets \((a,b,d)\) such that at least one point \(P\) (with integer coordinates) exists on \(AC\), making the three triangles \(ABP, CDP\) and \(BDP\) all similar.

For example, if \((a,b,d)=(2,3,4)\), it can be easily verified that point \(P(1,1)\) satisfies the above condition. Note that the triplets \((2,3,4)\) and \((2,4,3)\) are considered as distinct, although point \(P(1,1)\) is common for both.

If \(b+d<100\), there are \(92\) distinct triplets \((a,b,d)\) such that point \(P\) exists.

If \(b+d<100 000\), there are \(320471\) distinct triplets \((a,b,d)\) such that point \(P\) exists.

If \(b+d<100 000 000\), how many distinct triplets \((a,b,d)\) are there such that point \(P\) exists?

解决方案

可以发现，\(\angle DCP\)和\(\angle BAP\)必定是钝角。而在\(\triangle BDP\)中，最有潜力成为钝角的是\(\angle BPD\)。因此如果\(\triangle ABP,\triangle CDP,\triangle BDP\)相似，那么\(\angle DCP,\angle BAP,\angle BPD\)必定对应。且它们的大小都为\(\dfrac{3\pi}{4}\)。假设点\(P\)的坐标为\((x,y)\)，那么满足\(x+y=a\)。

  1. 如果\(\triangle DCP\sim \triangle PAB\)，那么有\(\dfrac{|DC|}{|PA|}=\dfrac{|CP|}{|AB|}=\dfrac{|DP|}{|PB|}\)，也就是\(\dfrac{d-a}{\sqrt2 y}=\dfrac{\sqrt2x}{b-a}\)，也就是\((d-a)(b-a)=2xy\)。
  2. 如果\(\triangle DCP\sim \triangle BAP\)，那么有\(\dfrac{|DC|}{|BA|}=\dfrac{|CP|}{|AP|}=\dfrac{|DP|}{|BP|}\)，也就是\(\dfrac{d-a}{b-a}=\dfrac{\sqrt2 x}{\sqrt2y}\)，也就是\((d-a)y=(b-a)x\)。

考虑如下两种不同的情况：\(\triangle DCP\sim \triangle DPB,\triangle DCP\sim \triangle BPD\)。

\(\triangle DCP\sim \triangle DPB\)

此时有\(\dfrac{|DC|}{|DP|}=\dfrac{|CP|}{|PB|}=\dfrac{|DP|}{|DB|}\)。

联合情况 1，可以知道有 \(\dfrac{|DC|}{|CP|}=\dfrac{|DP|}{|PB|}=\dfrac{|DC|}{|PA|}\)，也就是\(|CP|=|PA|\)，即\(x=y=\dfrac{a}{2}\)。这时就有\(2(d-a)(b-a)=a^2\).即\(a\)必须是偶数。

联合情况 2，可以知道有 \(\dfrac{|DC|}{|CP|}=\dfrac{|DP|}{|PB|}=\dfrac{|DC|}{|BA|}\)，也就是\(|CP|=|AB|\)，即\(\sqrt{2} x=b-a\)。这种情况是不可能出现的，因为回代到原式中，关于\((a,b,d)\)的式子一定会出现无理数系数\(\sqrt{2}\)。

\(\triangle DCP\sim \triangle BPD\)

因此可以得到\(\angle CDP=\angle PBD\)，以及比例关系：

\[\dfrac{|DC|}{|BP|}=\dfrac{|CP|}{|PD|}=\dfrac{|DP|}{|BD|}.\tag{B}\]

联合情况 1（\(\angle CDP=\angle APB\)），那么可以得到\(\angle APB=\angle PBD.\) 所以最终有\(PA\parallel BD.\)那么由于\(a=c\)，因此必然有\(b=d\)。

联立情况 2，那么基于情况 2 的相似条件，令\(k=\dfrac{|DP|}{|BP|}=\dfrac{x}{y}=\dfrac{d-a}{b-a}\)。此外由\(\dfrac{|CP|}{|PD|}=\dfrac{|DP|}{|BD|}\)，可以得知\(|DP|^2=|CP|\cdot|BD|\)。

由\((B)\)的第一、第三项，可以得到\(\dfrac{|DC|}{|BP|}=\dfrac{|DP|}{|BD|}\Longrightarrow|DC|\cdot|BD|=|DP|\cdot|BP|.\)代入\(k=\dfrac{|DP|}{|BP|}\)，得到\(|DC|\cdot|BD|=k|BP|^2.\)

再代入 \(k=\dfrac{d-a}{b-a}=\dfrac{|DC|}{|BA|}\)，即 \(k=\dfrac{|DC|}{b-a}\)，可约去 \(|DC|\)（因为 \(d>a\) 所以 \(|DC|>0\)）：\(|BD|=\dfrac{|BP|^2}{b-a}.\)

后得到\(|DP|^2 = |CP|\cdot|BD|= |CP|\cdot\dfrac{|BP|^2}{b-a}.\)

又因为\(|DP|^2 = k^2 |BP|^2\)，所以\(k^2=\dfrac{|CP|}{b-a}.\)代入\(k=\dfrac{x}{y}\) 与 \(|CP|=\sqrt2x\)后，得到\(\left(\dfrac{x}{y}\right)^2=\dfrac{\sqrt2x}{b-a}.\)最终化简得到：

\[ \sqrt{2}=\frac{x(b-a)}{y^2}. \]

右边是有理数（整数比），左边是无理数，矛盾。因此这个组合不可行。

接下来考虑对这两种情况进行计数。

\(2(d-a)(b-a)=a^2\)

通过化简，可以得到：

\[ 2(b-a)(d-a)=a^2 \Longleftrightarrow a^2-2a(b+d)+2bd=0 \Longleftrightarrow (b+d-a)^2=b^2+d^2. \]

令\(c=b+d-a\)，那么原式则等价于\(c^2=b^2+d^2.\)也就是 \((b,d,c)\) 是勾股三元组，且\(a=b+d-c, P=\left(\dfrac{a}{2},\dfrac{a}{2}\right).\)

因此这一类型的本质是：\(b,d\) 是一组勾股直角边，\(b+d\) 控制放大倍数；并且有序对 \((b,d)\) 与 \((d,b)\) 都算不同。

对每个原始勾股三元组，设两条直角边为 \(p,q\)，则 \(b+d=p+q\)，并且有序 \((b,d)=(p,q)\) 与 \((q,p)\) 都要计入，因此贡献

\[ 2\left\lfloor\frac{M-1}{p+q}\right\rfloor. \]

\(b=d\)

那么此时就得到\((b-a)^2=2xy\)，其中\(x+y=a\)。

尝试用一组标准参数化（等价于从勾股三元组出发）：取互素且一奇一偶的正整数 \(m>n\)，令\(x=2n^2,y=(m-n)^2.\)则\(a=x+y=2n^2+(m-n)^2\)

并且有\(2xy=2\cdot 2n^2\cdot (m-n)^2=(2n(m-n))^2,\)因此\(b-a=2n(m-n),\)从而\(b=a+2n(m-n)=m^2+n^2.\)

于是这类解就满足：

\[b=d=m^2+n^2\]

对每个原始勾股三元组斜边为 \(c\)，则 \(b+d=2c\)，贡献

\[ \left\lfloor\frac{M-1}{2c}\right\rfloor. \]

把所有原始勾股三元组的贡献累加，即得答案。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
from tools import *

N = 100000000

def count_triplets(M: int) -> int:
    """
    统计满足 b + d < M 的三元组 (a, b, d) 的数量（这里的计数逻辑来自题目的推导结果）。

    结论：可分为两类互不相交的家族（只需要枚举“原始”的勾股三元组，再按比例缩放计数）
    ----------------------------------------------------------------------
    设 lim = M - 1，则条件 b + d < M 等价于 b + d <= lim。

    Type 1（b != d）：
        b, d 是某个 primitive（原始）勾股三元组的两条直角边（legs）。
        若 primitive 的两边为 (b0, d0)，则所有缩放形式为 (b, d) = (t*b0, t*d0)。
        只要 t*(b0 + d0) <= lim，即 t <= lim // (b0 + d0)。
        对每个 primitive，合法的 t 个数为 lim // (b0 + d0)。

        由于 (b, d) 是“有序”的（ordered），(b0, d0) 与 (d0, b0) 都算不同，
        所以贡献要乘 2：
            contribution = 2 * (lim // (b0 + d0))。

    Type 2（b == d）：
        b (= d) 等于某个 primitive 勾股三元组的斜边（hypotenuse）c。
        若 primitive 斜边为 c0，则缩放后 b = d = t*c0。
        条件 b + d = 2*t*c0 <= lim，即 t <= lim // (2*c0)。
        贡献：
            contribution = lim // (2*c0)。

    ----------------------------------------------------------------------
    primitive 勾股三元组使用欧几里得公式（Euclid formula）生成：
        legs:
            p = m^2 - n^2
            q = 2mn
        hyp:
            c = m^2 + n^2
    条件：
        m > n
        gcd(m, n) = 1
        m - n 为奇数（即 m,n 一奇一偶）
    """

    # lim = M-1，后续统一用 “<= lim” 来表示 “< M”
    lim = M - 1
    ans = 0  # 累加答案

    # 从 m=2 开始枚举（m=1 时没有 n 满足 1<=n<m）
    m = 2
    while True:
        mm = m * m  # 预先计算 m^2，避免重复

        # -------------------- 全局提前停止（剪枝） --------------------
        # 对于固定的 m，随着 n 增大：
        #   s1 = (m^2 - n^2) + 2mn = p+q
        #   s2 = 2(m^2 + n^2) = 2c
        # 都会增长（至少不下降），因此只要“最小 n”的值都超过 lim，就没必要继续更大的 m。
        #
        # 1) 对 Type 1 的最小 (p+q) 通常在 n=1 处取得：
        #    s1_min(n=1) = (m^2 - 1) + 2m = m^2 + 2m - 1
        #
        # 2) 对 Type 2 的最小 2c 在 n=1 处：
        #    s2_min(n=1) = 2(m^2 + 1)
        #
        # 若这两个最小值都 > lim，则对于该 m 以及更大的 m 都不可能再贡献任何答案，直接 break。
        if (mm + 2 * m - 1) > lim and (2 * (mm + 1)) > lim:
            break

        # -------------------- 枚举 n（并保证 m-n 为奇数） --------------------
        # primitive 的条件要求 m,n 一奇一偶 <=> (m-n) 为奇数
        # 因此：
        #   若 m 为偶数，则 n 必须为奇数：从 1 开始步长 2
        #   若 m 为奇数，则 n 必须为偶数：从 2 开始步长 2
        start_n = 1 if (m & 1) == 0 else 2

        for n in range(start_n, m, 2):
            nn = n * n  # n^2

            # -------------------- 先算阈值，再决定是否提前 break --------------------
            # s1 对应 Type 1 的 (p+q)：
            #   p = m^2 - n^2
            #   q = 2mn
            #   s1 = p + q
            s1 = (mm - nn) + 2 * m * n

            # s2 对应 Type 2 的 (2c)：
            #   c = m^2 + n^2
            #   s2 = 2c
            s2 = 2 * (mm + nn)

            # 对固定 m，n 递增时 s1,s2 也递增；
            # 一旦 s1 与 s2 都 > lim，则更大的 n 只会更大，后续无需再看，直接 break n 循环。
            if s1 > lim and s2 > lim:
                break

            # primitive 条件之一：gcd(m,n)=1，否则得到的是非 primitive（会被更小的 primitive 缩放覆盖）
            if gcd(m, n) != 1:
                continue

            # -------------------- Type 1: b != d（两直角边） --------------------
            # 对应 primitive 的两直角边 (p,q)，缩放 t 倍后 (b,d)=(t*p, t*q)
            # 条件：t*(p+q) <= lim <=> t <= lim//(p+q)
            # 由于 (b,d) 视为有序对，所以 (p,q) 与 (q,p) 都算，乘 2
            if s1 <= lim:
                ans += 2 * (lim // s1)

            # -------------------- Type 2: b == d（斜边） --------------------
            # b=d=c，缩放 t 倍后 b=d=t*c0
            # 条件：2*t*c0 <= lim <=> t <= lim//(2*c0)
            if s2 <= lim:
                ans += lim // s2

        # 下一轮 m
        m += 1

    return ans


print(count_triplets(N))