987B. High School - Become Human

Mathematics

Year 2118. Androids are in mass production for decades now, and they do all the work for humans. But androids have to go to school to be able to solve creative tasks. Just like humans before.

It turns out that high school struggles are not gone. If someone is not like others, he is bullied. Vasya-8800 is an economy-class android which is produced by a little-known company. His design is not perfect, his characteristics also could be better. So he is bullied by other androids.

One of the popular pranks on Vasya is to force him to compare $x^{y}$ with $y^{x}$. Other androids can do it in milliseconds while Vasya’s memory is too small to store such big numbers.

Please help Vasya! Write a fast program to compare $x^{y}$ with $y^{x}$ for Vasya, maybe then other androids will respect him.

Hints

1. Think of a way to simplify $a^{b}$.

Solution

One of the very naive approach to this problem is to compare the values $x^{y}$ and $y^{x}$ using classic pow() function or we can first find the values of both $x^{y}$ and $y^{x}$ through modular exponentiation which has a time complexity of O(log n).

But huge values like ((109)^109) can’t be stored in C++, the maximum that can be stored is 10^18 using long long data type. So the solution shouldn’t involve the whole calculation.

$a^{b}$ can also be written as $b \times log(a)$.And $109 \times log(109)$ can be stored using long double data type without overflow. So just compare $y \times log(x)$ and $x \times log(y)$.

Code

#include <bits/stdc++.h>
using namespace std;

void fast(){ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);}

int main() {
  fast();

  long double a, b, x, y;
  cin >> x >> y;

  //STORING VALUES OF X^Y AND Y^X
  b = x*log(y);
  a = y*log(x);
  
  //COMPARISON OF VALUES
  if(a > b) cout << ">";
  else if(a < b) cout << "<";
  else if(a == b) cout << "=";
  return 0;
}

Written by Manoj