Cod sursa(job #2336569)

Utilizator TeodorLuchianovTeo Luchianov TeodorLuchianov Data 5 februarie 2019 11:28:34
Problema Ridicare la putere in timp logaritmic Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.65 kb
#include <fstream>

using namespace std;

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

unsigned int const modulo = 1999999973;

int pow(unsigned int n, unsigned int p, unsigned int left){
    if(p == 0){
        return 1;
    }else if(p == 1){
        return (1LL * n * left) % modulo;
    }else{
        if(p % 2 == 0){
            return pow((1LL * n * n) % modulo, p / 2, left);
        }else{
            return pow((1LL * n * n) % modulo, (p - 1) / 2, (left * n) % modulo);
        }
    }
}

int main()
{
    unsigned int n, p;
    in >> n >> p;
    out << pow(n % modulo, p, 1);
    return 0;
}
//4294967296 1999999973