Given 2 positive integers c and n, find any 2 positive integer answers for x and y that satisfy the following equation: √x + √y = √z where z = c²n.
Input
The first line of the input contains a single integer
t(1≤t≤105), the number of test cases. The first and only line of each test case consists of 2 space-separated integerscandn(4≤c²n≤1018, 2≤c≤109, 1≤n≤109)Output
For each test case output 2 space-separated positive integers
xandy, the answer to the equation.If there are multiple answers, print any.
I tried to make y = n, and then calculate x by quadratic analysis:
√x + √y = c*√n
=> x + 2√y√x + y = c²n
=> x + 2√y√x + y – c²n =0
Then, I calculated x by quadratic analysis:
=> x = (-b + √(b² – 4ac))/2a
Note: the time limit for this problem is 1.3 seconds, which means in the worst case I shouldn’t use more than 1010 or 1011 steps.
#include <iostream>
#include <cmath>
using namespace std;
int main()
{
int t, n , c;
double x, num1, num2;
cin >> t;
for(int i=0; i<t; i++)
{
cin >> c >> n;
num1 = (double)n - (pow(c, 2)*n);
num2 = (double) ((-2*sqrt(n))+sqrt((4*n)-(4*num1)))/2;
cout << (double)pow(num2 , 2) << ' ' << n;
}
}
I get the wrong answer but I don’t know what’s wrong.
Youssef Emad is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
7
Square both sides and you have x + y = z where z = c4n2.
Then let x = n2 and you get y = (c4 – 1)n2 = (c2 + 1)(c2 – 1)n2.
1
#include <iostream>
void solve_test_case() {
long long c, n;
std::cin >> c >> n;
// Strategy: Let's make x = (c-1)*(c-1)*n and y = n
// This ensures √x + √y = c√n
long long x = (c-1)*(c-1)*n;
long long y = n;
std::cout << x << " " << y << "n";
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int t;
std::cin >> t;
while (t--) {
solve_test_case();
}
return 0;
}
1