88 lines
1.4 KiB
C++
88 lines
1.4 KiB
C++
#include <iostream>
|
|
#include <cmath>
|
|
#include <set>
|
|
#include <algorithm>
|
|
using namespace std;
|
|
|
|
set<int> findFactors(int N) {
|
|
set<int> factors;
|
|
|
|
int stop = sqrt(N);
|
|
for (int i = 2; i <= stop; i++) {
|
|
if (N % i == 0) {
|
|
factors.insert(i);
|
|
factors.insert(N / i);
|
|
}
|
|
}
|
|
|
|
return factors;
|
|
}
|
|
|
|
|
|
|
|
bool areCoprimes(set<int> cFactors, int a, int b) {
|
|
auto setEnd = cFactors.end();
|
|
|
|
int stop = sqrt(a);
|
|
int i = 2;
|
|
|
|
for (i; i <= stop; i++) {
|
|
if (a % i == 0) {
|
|
int f1 = i;
|
|
int f2 = a / i;
|
|
|
|
if (b % f1 == 0 || b % f2 == 0 || cFactors.find(f1) != setEnd || cFactors.find(f2) != setEnd) {
|
|
return false;
|
|
}
|
|
} else if (b % i == 0) {
|
|
int f1 = i;
|
|
int f2 = b / i;
|
|
|
|
if (cFactors.find(f1) != setEnd || cFactors.find(f2) != setEnd) {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
|
|
stop = sqrt(b);
|
|
for (i; i <= stop; i++) {
|
|
if (b % i == 0) {
|
|
int f1 = i;
|
|
int f2 = b / i;
|
|
|
|
if (cFactors.find(f1) != setEnd || cFactors.find(f2) != setEnd) {
|
|
return false;
|
|
}
|
|
}
|
|
}
|
|
|
|
return true;
|
|
}
|
|
|
|
|
|
|
|
int main() {
|
|
int c;
|
|
cin >> c;
|
|
|
|
set<int> cFactors = findFactors(c);
|
|
|
|
|
|
uint64_t cSqr = pow(c, 2);
|
|
bool found = false;
|
|
for (int a = 1; a <= c; a++) {
|
|
uint64_t aSqr = pow(a, 2);
|
|
for (int b = a; b <= c; b++) {
|
|
if (aSqr + pow(b, 2) == cSqr && areCoprimes(cFactors, a, b)) {
|
|
cout << a << " " << b << " " << c << endl;
|
|
found = true;
|
|
}
|
|
}
|
|
}
|
|
|
|
if (!found) {
|
|
cout << "NOPE" << endl;
|
|
}
|
|
|
|
return 0;
|
|
} |