题目

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).

题解

第583题:海伦信封

标准信封的形状是矩形上面有个等腰三角形(封盖)。一个整数边长的信封如下所示。要形成一个有意义的信封,封盖(BCD)的高度必须小于矩形(ABDE)的高度。

示例信封不仅有整数边长,而且所有对角线(AC、AD、BD、BE 和 CE)的长度也是整数。这样的信封称为海伦信封

令 S(p) 是所有周长不超过 p 的海伦信封的周长的和。

已知 S(104) = 884680。求 S(107)。

预备知识

直角三角形的边长满足方程:x2 + y2 = z2《哈代数论(第6版)》第 13 章“某些 Diophantus 方程”第 2 节“方程 x2 + y2 = z2”定理 225:

定理 225 方程
                      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 是奇偶性相反的整数,且
                (a,b) = 1, a > b > 0.                       (13.2.4)
在 a, b 的不同值和 x, y, z 的不同值之间有一个一一对应关系。

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

定理 44 是无理数,除非 N 是一个整数 n 的 m 次幂。

推论 对于整数 N,如果 是有理数,则 是整数。

此外,我们还有:

定理 A 如果 a2 + b2 能被 4 整除,则 a 和 b 都是偶数。

证明:因为奇数的平方是奇数,偶数的平方是偶数,奇数加偶数是奇数,所以 a 和 b 不可能是一奇一偶。假设 a 和 b 都是奇数,则:a2 + b2 = (2m+1)2 + (2n+1)2 = 4(m2 + n2 + m + n) + 2,它不能被 4 整除。所以 a 和 b 都是偶数。

封盖的高度是整数

如上图,令:a = |AE| = |BD|, w = a/2 = |AF| = |BG|, b = |AC| = |CE|, c = |BC| = |CD|, g = |AB| = |DE| = |FG|, h = |CG|。则:

  • 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 都是整数。

三个直角三角形

本题的关键在于以下三个直角三角形:△BGC、△AFC 和 △AED。如上所述,这三个直角三角形的边长都是整数。容易验证,这三个直角三角形中每一个的直角边之和都小于海伦信封的周长的一半。这三个直角三角形之间有以下关系:

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

我们可以利用定理 225 来生成这些直角三角形,存储到适当的数据结构中,再挑选出满足以上条件的直角三角形。

解答

根据以上分析,我们有以下 C# 程序:

 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>());
12:     s.Add(v);
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)
24:         { Add(dict, u, v); Add(dict, v, u); }
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 中)

存储这些直角三角形的数据结构是:Dictionary<int,HashSet<int>>Key是直角边,Value是另外一个直角边的列表。例如,示例信封的数据如下(225 = 64 + 161):

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

这个程序的运行时间是 27 秒。

评论

推荐 1
这个 C# 并行程序在一台 8 CPU 的服务器上的运行结果:
$ mcs 407.cs && time mono 407.exe
39,7**,8*9,1*6,421

real 256m57.394s
user 2053m16.990s
sys 0m1.266s
这个 C# 并行程序是指:http://ideone.com/XtLkT7 –  黄志斌 01-08 15:38

推荐 1
C# 通过 System.Threading.Tasks.Parallel 类支持并行:
https://msdn.microsoft.com/zh-cn/library/system.threading.tasks.parallel.aspx
示例代码见:http://ideone.com/XtLkT7
这个代码用于暴力破解:https://projecteuler.net/problem=407
图灵社区:图书:C#并发编程经典实例 –  黄志斌 01-01 11:04
http://www.ituring.com.cn/book/1483 –  黄志斌 01-01 11:04
不错,表达式挺简单,比c++的thread好懂 –  lt 01-01 12:10

推荐 1
新年好.
请问c#如何支持并行?
我在我的程序中启用openmp,发现奇怪现象

b_2=b0;//lcm(b0,b1);

if(b_2*2 +b_2/b1*a1*2 >=MAXP) //b+ 2a+2h
break;
h=b_2/b0*a0; // 29.309s
因为b_2==b0,所以多余运算,如果改成更简单直接的如下,反而慢了
//h=a0; //33.441s
新年好。见我的 10:52 的评论。 –  黄志斌 01-01 10:53

推荐 1
我借用你的生成勾股数代码和pe论坛的二分代码,终于用我的办法做出来了
更新代码到了我的帖子 –  lt 2016-12-31 22:24

推荐 1
这题其实没有太多数论的东西,质数公式在75题已经考过了
Nice Numbers Birkhäuser 2016这本书也讲了不少数论的东西

推荐 1
比我的巧妙很多

推荐 1
卢涛老师在图灵社区有一篇相关的文章:
图灵社区:欧拉计划583题(海伦信封)
http://www.ituring.com.cn/article/273829

我要评论

需要登录后才能发言
登录未成功,请修改提交。