Cod sursa(job #2201466)
| Utilizator | Data | 4 mai 2018 20:39:09 | |
|---|---|---|---|
| Problema | Ridicare la putere in timp logaritmic | Scor | 100 |
| Compilator | cpp | Status | done |
| Runda | Arhiva educationala | Marime | 0.52 kb |
#include<fstream>
using namespace std;
ifstream cin("lgput.in");
ofstream cout("lgput.out");
const int m = 1999999973;
int main()
{
unsigned int i, n, p;
long long a, sol = 1;
cin>>n>>p;
a = n;
for (i = 0; (1<<i) <= p; ++ i) // Luam toti biti lui p la rand
{
if ( ((1<<i) & p) > 0) // Daca bitul i din p este 1 atunci adaugam n^(2^i) la solutie
sol= (sol * a) % m;
a=(a * a) % m; // Inmultim a cu a ca sa obtinem n^(2^(i+1))
}
cout<<sol; // Afisam solutia
}
