题目:题目链接
题意:对于直角三角形三边:x^2-y^2=z^2;题目中给出z^2,要求出最小的一组整数x和y。
分析:
1:将等式变形(x-y)(x+y)=z^2;
2:令A=x-y,B=x+y,T=z^2;于是A*B=T; x=(B+A)/2,y=(B-A)/2;
3:A和B是 T 的两个约数,只要A和B同时为奇数或者同时为偶数(B-A是偶数),就能保证x,y是整数;
4:找最小的一组,从sqrt(T)往下开始找T的约数,先找到的满足前面条件的就是最小的了。
巧妙的变幻推理:
#include <iostream> #include <cstdio> #include <string> #include <string.h> #include <map> #include <vector> #include <cstdlib> #include <algorithm> #include <cmath> #include <queue> #include <set> #include <stack> #include <functional> #include <fstream> #include <sstream> #include <iomanip> #include <numeric> #include <cassert> #include <bitset> #include <stack> #include <ctime> #include <list> #define INF 0x7fffffff #define max3(a,b,c) (max(a,b)>c?max(a,b):c) #define min3(a,b,c) (min(a,b)<c?min(a,b):c) #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; int gcd(int n,int m) { if(n<m) swap(n,m); return n%m==0?m:gcd(m,n%m); } int lcm(int n,int m) { if(n<m) swap(n,m); return n/gcd(n,m)*m; } #define N 10000007 int prime[N]; struct node { int x, y; }; bool cmp(const node & a, const node & b) { return a.x > b.x; } void getPrime(); void bash(); void wzf(); void SG(); int QuickMod(int a, int b, int n); int t, n; int main() { scanf("%d", &t); while(t--) { scanf("%d", &n); int tt =sqrt(1.0*n); int fp = 0; for(int i = tt; i >= 1; --i) { if(n % i==0) { int a = i; int b = n/a; if((a%2==1 && (b%2 == 1)) || (a%2==0 && b %2 == 0)) { //cout << "a: " << a << " b: " << b << endl; int x = (b-a)/2; int y = (a+b)/2; fp = 1; printf("%d %d\n", x, y); break; } } } if(!fp) printf("IMPOSSIBLE\n"); } return 0; } int QuickMod(int a,int b,int n) { int r = 1; while(b) { if(b&1) r = (r*a)%n; a = (a*a)%n; b >>= 1; } return r; } void getPrime() { memset(prime, 0, sizeof(prime)); prime[0] = 1; prime[1] = 1; for(int i = 2; i < N; ++i) { if(prime[i] == 0) { for(int j = i+i; j < N; j+=i) prime[j] = 1; } } } void bash(int n, int m) { if(n%(m+1) != 0) printf("1\n"); else printf("0\n"); } void wzf(int n, int m) { if(n > m) swap(n, m); int k = m-n; int a = (k * (1.0 + sqrt(5.0))/2.0); if(a == n) printf("0\n"); else printf("1\n"); } int numsg[N]; void SG(int n) { int sum = 0; for(int i=0; i < n; i++) { scanf("%d",&numsg[i]); sum ^= numsg[i]; } if(sum == 0) printf("No\n"); else { printf("Yes\n"); for(int i = 0; i < n; i++) { int s = sum ^ numsg[i]; if(s < numsg[i]) printf("%d %d\n", numsg[i], s);//从有num[i]个石子的堆后剩余s个石子 } } }