Cod sursa(job #526757)
Utilizator | Vasilut Lucian lucian666 | Data | 29 ianuarie 2011 13:14:38 |
---|---|---|---|
Problema | Ridicare la putere in timp logaritmic | Scor | 10 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.5 kb |
#include<iostream>
#include<fstream>
using namespace std;
int putere_binara(int baza,long long int expo,long int n)
{
int i;
baza%=n;
int b[50],nrb=0;
for(;expo;expo/=2)
b[++nrb]=expo%2;
int rez=1;
for(i=nrb;i;i--)
{
rez=(rez*rez)%n;
if(b[i])
rez=(rez*baza)%n;
}
return rez;
}
int main()
{
ifstream fin("lgput.in");
ofstream fout("lgput.out");
int baza;
long long int expo;
fin>>baza>>expo;
fout<<putere_binara(baza,expo,1999999973);
return 0;
}