勾股数组 | HDU3422

作者: 0与1的邂逅 | 来源:发表于2019-03-01 20:24 被阅读0次

勾股数组 | HDU3422
勾股元数组
345勾股
勾股定律
2020-01-19（学习笔记）
数论 | 勾股数组
探索勾股数组
v-model checkbox
五维阅读课第4次作业
复选框表格单选，多选、全选下标删除逻辑

HDU3422 Triangle

Problem Description
K likes to play with the balls.That day he piled a triangle (n layers, layer 1 start,the first layer has 1 ball,the secode layer has 2 balls,……,the nth layer has n balls), but he felt uncomfortable after completion, and want to pile a right triangle, because he felt that the number 4 is a lucky one (because of “si ji fa cai”). So he decided to use 4 times of the balls he just used as a right-edge side of the right triangle(the three edges have no common factor).He only to pile the three edges,that is the middle is empty.But there will not have so many balls,so he wants to know the minimum of balls he must use.Now ,he turn to you for help.

Input
The layer of the triangle as the promble describes n,1 <= n < 2^16

Output
The minimum of balls he must use and the length of the hypotenuse. One case one line

Sample Input
1
2
3

Sample Output
9 5
27 13
53 25

The second case:
Let the right_edge promble describles is b ,The layer is 2,so b is 4 * (1 + 2) = 12.wo can know the edges of
right triangle is 5 , 12 ,13.
So the minimum of balls he must use is (5 + 12 + 13 – 3) = 27

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3422

思路：

题目题意是将球摆成三角形问题，这跟我们介绍勾股数组时的一个例子相同。

根据题目例子给出的提示，我们将问题进行转换：

将4*（1+2+...+n）作为直角三角形一条直角边，求此时该三角形的最小斜边的值，以及此时三角形的周长-3的值。

PS：为什么是三角形的周长-3，因为题目是要求摆成此三角形需要的最小的球数，而在计算三角形的周长过程，三角形的三个顶点的三个球会被重复计算两次。

首先计算1+2+...+n，很明显这是一个等差数列的和，根据等差数列求和公式可得 $\sum_{i=1}^{n} i=\frac{(1+n)n}{2}$ 故直角边 $b=4\sum_{i=1}^{n} i=2(1+n)n$ 再根据勾股数组定理 $a=st,b=\frac{s^2-t^2}{2},c=\frac{s^2+t^2}{2}$ 其中s>t≥1是没有大于1的公因数的奇数。

分析推导的过程：
∵ $\frac{s^2-t^2}{2}=2(1+n)n$
∴ $s^2=4(1+n)n+t^2=4n^2+4n+t^2$
∵ 直角三角形一直角边为定值，另一直角边越长，斜边就越长
∴ 令另一直角边 $a=st$ 最小
$a^2$
$=t^2s^2$
$=t^2(4n^2+4n+t^2)$
$=t^4+(4n^2+4n)t^2$
$=t^4+2(2n^2+2n)t^2【凑完全平方】$
$=t^4+(4n^2+4n)t^2+(2n^2+2n)^2-(2n^2+2n)^2$
$=(t^2+2n^2+2n)^2-(2n^2+2n)^2$
∵ $t>0且t∈Z$
∴ $a>0$
∴ 当 $t=1$ 时， $a^2$ 最小，即a最小
故此时
$s^2=4n^2+4n+t^2=4n^2+4n+1=(2n+1)^2$
$s=2n+1$
$∴ 斜边长c=\frac{s^2+t^2}{2}=\frac{4n^2+4n+2}{2}=2n^2+2n+1$

$周长C=a+b+c=st+\frac{s^2-t^2}{2}+\frac{s^2+t^2}{2}=s+s^2=4n^2+6n+2$
∴ 输出 $4n^2+6n-1 , 2n^2+2n+1$ 即可

实现代码：

// HDU 3422
// 勾股数组定理 
// 0MS 1372K G++

#incl1ude<iostream>
#include<cstdio>
using namespace std;
int main()
{
    int n;
    while(~scanf("%d",&n))
    {
        // 注意要选择G++，C++则会WA 
        // 因为n不大于2^16,n*n会超过int范围（溢出）
        // 因此需要输出为long long类型 
        printf("%lld %lld\n",4*n*n+6*n-1,2*n*n+2*n+1);
        // printf("%I64d %I64d\n",4*n*n+6*n-1,2*n*n+2*n+1); 
        // 两种形式都可以 
    }
}