Cod sursa(job #1772983)

Utilizator HuskyezTarnu Cristian Huskyez Data 7 octombrie 2016 12:51:19
Problema Ridicare la putere in timp logaritmic Scor 10
Compilator cpp Status done
Runda Arhiva educationala Marime 0.45 kb
#include <iostream>
#include <fstream>

#define infile "lgput.in"
#define outfile "lgput.out"
#define mod 1999999973

using namespace std;

ifstream in(infile);
ofstream out(outfile);

int x, p;

int putere(int x, int p)
{
    if(p == 0) return 1;
    if(p == 1) return x%mod;

    if(p%2 == 0) return putere(x*x, p/2)%mod;
    if(p%2 == 1) return (x*putere(x*x, (p-1)/2))%mod;
}

int main()
{

    in >> x >> p;

    out << putere(x, p) << '\n';

    return 0;
}