 # REC09B - Editorial

Johnny Bravo

Author: Rishabh Sethi
Tester: Abhishek Chaudhary
Editorialist: Rishabh Sethi

EASY

Math

# PROBLEM:

Given two integers A and B, we have to find two integers C and D such that value of (C^{2}+D^{2}) is greater than value of (A^{2}+B^{2}) and the multiplication of (A^{2}+B^{2}) and (C^{2}+D^{2}) results into sum of square of two integers X and Y. Furthermore, the value of (X^{2}+Y^{2}) should be minimum.

# QUICK EXPLANATION:

Firstly we need to find all the integer value of C and D such that (A^{2}+B^{2})*(C^{2}+D^{2}) results into sum of squares of two integers. It can be easily proved that whatever be the value of C and D, the multiplication will always result into sum of sqaures of two integers. With this proved, we can find C and D such that the value of C^{2}+D^{2} is just greater than A^{2}+B^{2}. Since the values of C and D are less than 2000, we can easily use brute force to find the values.

# EXPLANATION:

Firstly we need to prove that whatever be the value of C and D, (A^{2}+B^{2})*(C^{2}+D^{2}) results into sum of squares of integers.
Let P and Q be two complex numbers.
P = a + ib
Q = c + id
Since multiplication of 2 complex number results into yet another complex number,thus on multiplying these two numbers we have
X = P*Q
x + iy = (a + ib)*(p + iq)
Now, taking magitude and sqauring on both sides, we have
(x^{2} + y^{2}) = (a^{2} +b^{2})*(p^{2} + q^{2})

Thus we can see that the above equation is independent of values of a,b,p and q.
Now, on iterating over all possible values of C and D, we find the values of C^{2} + D^{2} such that it is just greater than A^{2} + B^{2}.

``````For all C from 1 to 2000
For all D from C+1 to 2000
If C^2 + D^2 > A^2 + B^2 and C^2 + D^2<=Minimum value
Minimum Value = C^2 + D^2
If C^2 + D^2 == Minimum Value and C + D < Minimum Sum
Final C, D = C,D
Elif C^2 + D^2<Minimum Value
Minimum Value = C^2 + D^2
Minimum Sum = C+D
Final C, D = C, D
``````

# SOLUTIONS:

Setter's Solution
``````#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
int t;
cin>>t;
while(t--){
int a, b;
cin>>a>>b;
int p = a*a + b*b;
int mn1 = 10000000, mn2 = 10000000;
int c = 2000, d = 2000;
for(int i=1; i<=2000; i++){
for(int j=i; j<=2000; j++){
int q = i*i + j*j;
if(q>p){
if(q<=mn1){
if(q==mn1){
if(i+j<mn2){
mn2 = i + j;
c = i;
d = j;
}
}
else{
mn1 = q;
mn2 = i + j;
c = i;
d = j;
}
}
}
}
}
cout<<c<<" "<<d<<endl;
}
return 0;
}
``````
Tester's Solution
``````#include<bits/stdc++.h>
using namespace std;
typedef long  long ll;

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);

ll t;
cin>>t;
while(t--)
{
ll x,y,mn=1e17,c=1e17,d=1e17;
cin>>x>>y;
ll sm1=(x*x + y*y);
for(ll i=1;i<=2000;i++)
{
for(ll j=i;j<=2000;j++)
{
if((i*i + j*j)>sm1)
{
if((i*i + j*j)*sm1<=mn)
{
if((i*i + j*j)*sm1==mn)
{
if(i+j<c+d )
{
c=i;
d=j;
}
assert(i+j==c+d);
}
else
{
mn=(i*i + j*j)*sm1;
c=i;
d=j;
}
}
}
}
}
cout<<c<<" "<<d<<"\n";
}
}
``````
2 Likes

The following is my 15 lines of code C++14 solution of this problem using binary search.

https://www.codechef.com/viewsolution/27908802

1 Like

Yeah, I later on realized that the question can be done with binary search. One for loop for C and inside the For loop binary search D from 1 to 2000. Had the constraint been of the around 10^5, it would have been fun.

1 Like