Cod sursa(job #644688)

Utilizator tak3rStefan Mirea tak3r Data 7 decembrie 2011 14:24:37
Problema Ridicare la putere in timp logaritmic Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.61 kb
#include<iostream>
#include<cstdio>

using namespace std;

long long toPower( int n, int p ){
  
  long long num = n;
  int k, r, i;
  long long a[128];
  
  if( p == 0 ){
    return 1;
  }
  if( p < 0 ){
    //TODO
  }
  
  a[0] = 1;
  a[1] = n;
  for( k=2; k<=p; k*=2 ){
    num *= num;
    a[k] = num;
  }
  
  k/=2;
  r = p - k;
  for( i=k; r>0; i/=2 ){
    if( r-i >= 0 ){
      num *= a[i];
      r -= i;
    }
  }
  
  return num;
}

int main(){
  
  int n,p;
  
  freopen( "lgput.in", "r", stdin );
  freopen( "lgput.out", "w", stdout );

  scanf( "%d %d", &n, &p );

  printf( "%lld\n", toPower( n, p ) );
  
}