PROBLEM LINK:
Author: Rishabh Sethi
Tester: Abhishek Chaudhary
Editorialist: Rishabh Sethi
DIFFICULTY:
EASY
PREREQUISITES:
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";
}
}