Cod sursa(job #868244)
Utilizator | adrian dumitrache addy01 | Data | 30 ianuarie 2013 20:50:45 |
---|---|---|---|
Problema | Ridicare la putere in timp logaritmic | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.62 kb |
#include <iostream>
#include<cstdio>
using namespace std;
const int mod=1999999973;
int logput(int x,int p)
{
if(p == 0)
return 1;
else if(p == 1)
return x;
int ret = 1;
if(p % 2 == 0)
{
ret = logput(x,p/2);
ret *= ret;
ret %= mod;
}
else
{
ret = logput(x,(p-1)/2);
ret *= ret;
ret *= x;
ret %= mod;
}
return ret;
}
int main()
{
freopen("rptl.in","r",stdin);
//freopen("rptl.out","w",stdout);
int x,p;
cin>>x;
cin>>p;
cout<<logput(x,p);
return 0;
}