# 题目

Problem 583. Heron Envelopes

A standard envelope shape is a convex figure consisting of an isosceles triangle (the flap) placed on top of a rectangle. An example of an envelope with integral sides is shown below. Note that to form a sensible envelope, the perpendicular height of the flap (BCD) must be smaller than the height of the rectangle (ABDE).

In the envelope illustrated, not only are all the sides integral, but also all the diagonals (AC, AD, BD, BE and CE) are integral too. Let us call an envelope with these properties a Heron envelope.

Let S(p) be the sum of the perimeters of all the Heron envelopes with a perimeter less than or equal to p.

You are given that S(104) = 884680. Find S(107).

# 预备知识

x2 + y2 = z2                             (13.2.1)

x > 0, y > 0, z > 0, (x,y) = 1, 2|x            (13.2.2)

x = 2ab, y = a2 - b2, z = a2 + b2,         (13.2.3)

(a,b) = 1, a > b > 0.                       (13.2.4)

《哈代数论（第6版）》第 4 章“无理数”第 3 节“Pythagoras 定理及其推广”定理 44：

# 封盖的高度是整数

• h2 = c2 - (a/2)2, (2h)2 = 4c2 - a2, 即：(2h)2 是整数。
• b2 = (a/2)2 + (g+h)2, 8gh = 4b2 - 4g2 - 4h2 - a2，即：2h 是有理数。
• 根据定理 44 的推论，2h 是整数。
• 4c2 = a2 + (2h)2，根据定理 A，a 和 2h 都是偶数。所以 w 和 h 都是整数。

# 三个直角三角形

• |AE| = 2|AF|
• |DE| > |GC|
• |FC| = |DE| + |GC|

# 解答

`````` 1: using System;
2: using System.Collections.Generic;
3:
4: static class E583
5: {
6:   static int Gcd(int a, int b) { return b == 0 ? a : Gcd(b, a%b); }
7:
8:   static void Add(Dictionary<int,HashSet<int>> d, int k, int v)
9:   {
10:     HashSet<int> s;
11:     if (!d.TryGetValue(k, out s)) d.Add(k, s = new HashSet<int>());
13:   }
14:
15:   static Dictionary<int,HashSet<int>> GetTs(int m)
16:   {
17:     var dict = new Dictionary<int,HashSet<int>>();
18:     for (int a = 2; ; a++) {
19:       var done = true;
20:       for (int x, y, b = 1; b < a; b++) {
21:         if ((x = a*b << 1) + (y = a*a - b*b) >= m) break;
22:         if ((1 & (a + b)) == 0 || Gcd(a, b) != 1) continue;
23:         for (int u = x, v = y; u + v < m; u += x, v += y)
25:         done = false;
26:       }
27:       if (done) break;
28:     }
29:     return dict;
30:   }
31:
32:   static void Main()
33:   {
34:     int n = (int)1e7; long z = 0; var ts = GetTs(n >> 1);
35:     foreach (var kvp in ts) {
36:       var w = kvp.Key; HashSet<int> vs, us = kvp.Value;
37:       if (!ts.TryGetValue(w + w, out vs)) continue;
38:       foreach (var h in us) {
39:         int p, f = w + (int)Math.Sqrt((long)h*h + (long)w*w);
40:         foreach (var g in vs)
41:           if (g > h && (p = (f+g)<<1) <= n && us.Contains(g+h))
42:             z += p;
43:       }
44:     }
45:     Console.WriteLine(z);
46:   }
47: }
``````

• GetTs 方法生成所有直角边之和小于 107/2 的整数边直角三角形。
• 第 24 行把生成的直角三角形加入到字典中，每个三角形加入两次，每个直角边各一次。
• 第 35 行的 foreach 循环遍历这些直角三角形。
• 第 36 行的 w = |BG| 是的 △BGC 的直角边。
• 第 37 行判断是否存在直角边为 2w = |AE| 的直角三角形。
• 第 38 行的 foreach 循环遍历 △BGC 的另一个直角边 h = |GC|。
• 第 39 行的 f = w + c = |BG| + |BC|。
• 第 40 行的 foreach 循环遍历 △AED 的直角边 g = |ED|。
• 第 41 行判断这三个直角形是否满足前述条件。（△AFC 体现在 g+h 中）

120: 90 160 50 288 64 225 35 ... 3599
240: 180 ... 418 161 2394 782 2875 551 3596 1591