Cod sursa(job #2057788)

Utilizator MrRobotMrRobot MrRobot Data 4 noiembrie 2017 19:19:58
Problema Ridicare la putere in timp logaritmic Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.79 kb
#include <iostream>
#include <fstream>
using namespace std;

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

int exp_log (int n, int p)
{
    if (p == 0)
        return 1;
    if (p == 1)
        return n;
    if (p%2 == 0)
        return (exp_log(n*n, p/2));
    if (p%2 == 1)
        return (n*exp_log(n*n, (p-1)/2));
}

int main()
{
    long long n, p;
    fin>>n>>p;
    //fout<<exp_log(n, p);
    if(p == 0)
        fout<<1;
    else
    {
        long long x =1;
        while(p>1)
        {
            if(p%2 == 0)
            {
                n = n*n;
                p=p/2;
            }
            else
            {
                x = n*x;
                n = n*n;
                p = (p-1)/2;
            }
        }
        fout<<x*n;
    }
}