Масивні числа#1213

Масивні числа (Розбір)

Логарифм – це монотонно зростаюча функція, тому якщо $x < y$ x < y, то $l o g (x) < l o g (y)$ log(x) < log(y).

Прологарифмуємо нерівність: $a^{b} < c^{d}$ a^b < c^d. Візьмемо, наприклад, десятковий логарифм (чи натуральний, різниці немає):

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

b \cdot lg a < d \cdot lg c

Отже, порівняння двох великих чисел зводиться до порівняння двох чисел $b \cdot l g a$ b \cdot lg a і $d \cdot l g c$ d \cdot lg c. Значення виразів $b \cdot l g a$ b \cdot lg a і $d \cdot l g c$ d \cdot lg c знаходяться в типі $d o u b l e$ , тому їх можна легко порівняти.

Реалізація алгоритму

Читаємо вхідні дані, виділяючи основи і показники степенів для кожного числа.

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

Порівняємо значення прологарифмованих виразів $b \cdot l g a$ b \cdot lg a і $d \cdot l g c$ d \cdot lg c, після чого виведемо відповідь.

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 реалізація

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++