It turns out that 12 cm is the smallest length of wire that can be bent to form an integer sided right angle triangle in exactly one way, but there are many more examples.
12 cm: (3,4,5)
24 cm: (6,8,10)
30 cm: (5,12,13)
36 cm: (9,12,15)
40 cm: (8,15,17)
48 cm: (12,16,20)
In contrast, some lengths of wire, like 20 cm, cannot be bent to form an integer sided right angle triangle, and other lengths allow more than one solution to be found; for example, using 120 cm it is possible to form exactly three different integer sided right angle triangles.
120 cm: (30,40,50), (20,48,52), (24,45,51)
Given that L is the length of the wire, for how many values of L 1,500,000 can exactly one integer sided right angle triangle be formed?
Note: This problem has been changed recently, please check that you are using the right parameters.
下面是java解题方法:
public static void main(String[] args) {
Map<Integer, ABC> dict = new HashMap<Integer, ABC>();
int L = 1500000;
int M = (int)Math.sqrt(L / 2);
for (int m = 1; m <= M; m++) {
for (int n = 1; n < m; n++) {
int a = m * m - n * n;
int b = 2 * m * n;
int c = m * m + n * n;
int l = a + b + c;
int k = L / l;
for (int i = 1; i <= k; i++) {
int[] abc = { i * a, i * b, i * c };
Arrays.sort(abc);
check(i, l, abc, dict);
}
}
}
int count = 0;
for (ABC abc : dict.values()) {
count += abc.got;
}
System.out.println(count);
}
private static void check(int i, int l, int[] abc, Map<Integer, ABC> dict) {
int ll = i * l;
ABC tmp = dict.get(ll);
if (tmp != null) {
if (tmp.got == 1) {
int[] tmp1 = tmp.abc;
for (int x = 0; x < 3; x++) {
if (tmp1[x] != abc[x]) {
tmp.got = 0;
break;
}
}
}
} else {
dict.put(ll, new ABC(abc));
}
}
static class ABC {
public ABC(int[] abc) {
this.abc = abc;
}
int got = 1;
int[] abc;
}
这个解法的时间在秒级,解法利用了下面勾股数的性质:
1,通过a = m^2 − n^2, b = 2mn, c = m^2 + n^2 (1)可以生成所有的素勾股数和一部分派生勾股数(a,b,c),其在(m>n,m,n为正整数);
2,勾股数分为素勾股数和派生勾股数,而且所有派生勾股数都是由素勾股数派生而来的;
3,根据1,2,利用式(1),遍历m,n并加上派生规则可以生成所有勾股数。
注:正整数a,b,c满足a^2+b^2=c^2<=>(a,b,c)是勾股数,如果(a,b,c)=1(即a,b,c互素),则(a,b,c)称为素勾股数,对于整数k,(ka,kb,kc)是由(a,b,c)派生的勾股数。
分享到:
相关推荐
solution to problem 5
project_euler Project Euler 问题的解决方案 ###Problem 1 - 3 和 5 的倍数### 如果我们列出所有 10 以下是 3 或 5 的倍数的自然数,我们得到 3、5、6 和 9。这些倍数的和是 23。求1000 以下所有 3 或 5 的倍数之...
项目欧拉使用Javascript在解决Project Euler问题
项目-euler-问题-下载器 将所有 projecteuler.net 问题下载到您的本地存储
以Python语言来解Project Euler问题。 Project Euler: 针对数学和程式爱好者,设计了一系列的问题,至今已有五百多道,供大家挑战,每一题都要求应在1分钟内计算出答案。我使用硬体Raspberry Pi 2与软体Raspbian,...
Project-Euler-Problem-8
欧拉 收集有关问题的解决方案。 每个模块都包含一个问题的解决方案。 euler / data目录中包含解决方案的所有必要数据。 安装 ...[0.08013 sec] euler.problem_45.solve() = 1533776805 [0.04725 sec]
#Project Euler 问题 2 偶数斐波那契数列
#Project Euler 问题 1 3 和 5 的倍数
This is a solution the problem 67 of Project Euler website: https://projecteuler.net/archives
##用法首先,您需要创建一个project-euler目录并cd进入该目录。 $ mkdir project-euler && cd project-euler Usage: euler [options] Options: --version output the version number -h, --help output usage ...
各种编程语言中已解决的Project Euler问题的集合。 如何贡献 请为每种不同的编程语言创建一个单独的文件夹。 为每个问题陈述创建一个单独的文件夹。 将解决方案的文件名设置为您的github用户名。 示例: Python/...
欧拉项目解决方案 由 Kenny Wibowo 用 Java 创建 依赖关系 需要以下内容来编译和清理: java ant 编译 要编译代码,请在根目录中运行以下任一命令: ant ... java main/Main [problem number]
ProjectEuler 一系列具有挑战性的数学/计算机编程问题网站: :
多种语言的欧拉 使用不同编程语言的解决方案。 C C ++ Clojure 椰子 水晶 d 长生不老药 Erlang F# ... 运行ruby scripts/add_new_problem.rb将新问题添加到项目中。 有关更多信息,请单击。
欧拉计划(Project Euler)是一系列具有挑战性的问题,需要数学和编程技巧。 谁喜欢学习数学的新领域,欧拉项目将是一个有趣的旅程。 如何贡献? 分叉此存储库。 在您要解决的语言的目录中,使用格式problem_number....
Problem 1: Multiples of 3 and 5 If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23. Find the sum of all the multiples of 3...
bundle exec ruby -Ispec spec/project_euler/problem_001_acceptance.rb 执照 麻省理工学院执照 Copyleft(C)2011-2015 Victor Koronen 特此免费授予获得此软件和相关文档文件(“软件”)副本的任何人无限制地...
欧拉公式求长期率的matlab代码欧拉经理 通过命令行管理问题。...include_images会将Project Euler的图像复制到euler托管目录中,这样您就可以在没有Internet连接的情况下访问它们。 $ euler include_imag
Euler)是一系列具有挑战性的数学/计算机编程问题,不仅需要数学方面的知识来解决,还需要更多。 尽管数学将帮助您找到优雅而有效的方法,但仍需要使用计算机和编程技巧来解决大多数问题。 要了解有关欧拉计划的更多...