Massive Numbers#1213

Massive Numbers (Editorial)

A logarithm is a monotonically increasing function, so if $x < y$ x < y, then $l o g (x) < l o g (y)$ log(x) < log(y).

Let's take the logarithm of the inequality: $a^{b} < c^{d}$ a^b < c^d. For example, using the common logarithm (or natural logarithm, it doesn’t matter):

b \cdot l g a < d \cdot l g c

b \cdot lg a < d \cdot lg c

Therefore, comparing two large numbers reduces to comparing the two values $b \cdot l g a$ b \cdot lg a and $d \cdot l g c$ d \cdot lg c. The values of $b \cdot l g a$ b \cdot lg a and $d \cdot l g c$ d \cdot lg c fit into a $d o u b l e$ type, so they can be easily compared.

Algorithm implementation

Read the input data. Extract the bases and exponents for each number.

scanf("%d^%d %d^%d",&a,&b,&c,&d);

Compare the values of the logarithmized expressions $b \cdot l g a$ b \cdot lg a and $d \cdot l g c$ d \cdot lg c. Then print the answer.

if (b * log(1.0 * a) < d * log(1.0 * c)) printf("%d^%d\n",c,d);
else printf("%d^%d\n",a,b);

Java implementation

import java.util.*;

public class Main
{
  public static void main(String[] args)
  {
    Scanner con = new Scanner(System.in);
    String s = con.nextLine();
    StringTokenizer st = new StringTokenizer(s," ^");
    int a = Integer.valueOf(st.nextToken()),
        b = Integer.valueOf(st.nextToken()),
        c = Integer.valueOf(st.nextToken()),
        d = Integer.valueOf(st.nextToken());
    if(b * Math.log(a) > d * Math.log(c)) 
      System.out.println(a + "^" + b);
    else 
      System.out.println(c + "^" + d);
    con.close();
  }
}

C++