Heron and His Triangle HDU - 6222（pell 大数）
发布时间：2020-12-14 05:14:27 所属栏目：大数据 来源：网络整理
导读：---恢复内容开始--- Heron and His Triangle Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 262144/262144 K (Java/Others) Total Submission(s): 2543????Accepted Submission(s): 1060 Problem Description A triangle is a Heron’s triangle
|
---恢复内容开始--- Heron and His TriangleTime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 262144/262144 K (Java/Others)
Problem Description
A triangle is a Heron’s triangle if it satisfies that the side lengths of it are consecutive integers t−1,t,t+ 1 and thatits area is an integer. Now,for given n you need to find a Heron’s triangle associated with the smallest t bigger
than or equal to n.
?
?
Input
The input contains multiple test cases. The first line of a multiple input is an integer T (1 ≤ T ≤ 30000) followedby T lines. Each line contains an integer N (1 ≤ N ≤ 10^30).
?
?
Output
For each test case,output the smallest t in a line. If the Heron’s triangle required does not exist,output -1.
?
?
Sample Input
4 1 2 3 4
?
?
Sample Output
4 4 4 4
?
?
Source
2017ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）
?
?
Recommend
jiangzijing2015
? 遇到求三角形面积且已知三边长 那就用海伦公式
? ? ? Heron and His TriangleTime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 262144/262144 K (Java/Others)
Problem Description
A triangle is a Heron’s triangle if it satisfies that the side lengths of it are consecutive integers t−1,monospace'>
4 4 4 4
?
?
Source
2017ACM/ICPC亚洲区沈阳站-重现赛（感谢东北大学）
?
?
Recommend
jiangzijing2015
首先根据题意设a=t-1，b=t，c=t+1，这样我们可由海伦凯勒公式得到 ? ? ? ? ? ? ? ? ? ? ? ? ? ? 那么要想使得s为整数，就要使? ? ? 等于3乘以一个平方数 所以我们设? ? ? ? ? ?? 于是得到? ? ? ? ? ? ? ?d=3 根据题意可知最小特解为x=2，y=1；
打个表之后发现这样一些数字4,14,52,194,724,2702....然后得出递推式子，F[n]=4*F[n-1]-F[n-2];由于n非常的大，所以矩阵快幂维护也不行。最后考虑这样的数字几乎增长比较快，那么范围内这样的数字就会比较少，不想用高精度的可以考虑用java大数了，用个list将所有n范围内的结果保存一下，最后直接查询就可以了。 （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
