Cod sursa(job #2646804)

Utilizator fredtuxFlorin Dinu fredtux Data 2 septembrie 2020 00:37:38
Problema Ridicare la putere in timp logaritmic Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.55 kb
#include <fstream>

using namespace std;

int exp_by_squaring(int x, int exp);

int main() {
  ifstream fin("lgput.in");
  ofstream fout("lgput.out");

  int x, exp;
  fin >> x >> exp;

  fout << exp_by_squaring(x, exp);

  return 0;
}

int exp_by_squaring(int x, int exp) {
  if (exp < 0) return exp_by_squaring(1 / x, -exp);

  if (exp == 0) return 1;
  if (exp == 1) return x;

  int y = 1;
  while (exp > 1) {
    if (exp % 2 == 0) {
      x *= x;
      exp /= 2;
    } else {
      y = x * y;
      x *= x;
      exp = (exp - 1) / 2;
    }
  }

  return x * y;
}