2015浙工大校赛-Problem C: 三角形-(费马大定理)
2015浙工大校赛-Problem C: 三角-(费马大定理)
Submit: 375 Solved: 56
[Submit][Status][Web Board]
链接:http://acm.zjut.edu.cn/onlinejudge/problem.php?cid=1101&pid=2
题面:
Problem C: 三角
Time Limit: 1 Sec Memory Limit: 32 MBSubmit: 375 Solved: 56
[Submit][Status][Web Board]
Description
有个直角三角形三边为A,B,C三个整数。已知C为最长边。现告诉你A的长度,求一组B,C,使得B和C最接近
Input
单行输入一个整数2 < A < 100000000,直到文件结束(组数小于10000)
Output
单行输出一个整数B C
Sample Input
3
Sample Output
4 5
法一:
费马大定理:平方整数解a^2+b^2=c^2的a值奇偶数列法则可知。
当a为奇数时,
a=2n+1
c=n^2+(n+1)^2
b=c-1
当a为偶数时,
a=2n+2,
c=1+(n-1)^2
b=c-2
法二:
找规律,根据法一的结果,可能多试几组就能发现规律,不过还是要够胆量猜才行。
a为奇数时c-b=1,偶数时c-b=2。
法三:
这是我自己在做的时候的思路。
设b为x,c就等于sqrt(a^2+x^2),求(c-b)min,很直接的求了导,发现小于0。那就纳闷了,那不是无限嘛,一直怀疑自己求错了,可是求了好多遍,都是小于0。但也不是所有都可以,必须是整数解,苦恼了好久,wa了好几次。突然灵机一动,既然是要求最小差,那就从小到大枚举最小差,不就好了嘛!
设差值为x,那么c为b+x,a^2+b^2=(b+x)^2,化简后得到2b=(a^2-x^2)/x,只要可以整除此时的x即为最小差值,求出相应的b、c即可。
收获:
虽然是道简单题,但还是说明了转换思维的重要性,为什么一定要枚举b,不直接枚举差值呢!
代码:
#include <iostream> #include <cstring> #include <cstdio> #include <string> #include <iomanip> #include <vector> #include <map> #include <set> #include <algorithm> #include <queue> #include <cmath> using namespace std; int main() { long long int a,b,c; while(cin>>a) { for(long long int i=1;;i++) { if((a*a-i*i)%(2*i)==0) { b=(a*a-i*i)/(2*i); c=b+i; break; } } cout<<b<<" "<<c<<endl; } }