Cod sursa(job #604321)
Utilizator | Data | 21 iulie 2011 17:25:49 | |
---|---|---|---|
Problema | Ridicare la putere in timp logaritmic | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.49 kb |
# include <fstream>
using namespace std;
const long long prim = 1999999973;
int main(){
ifstream fin ("lgput.in");
ofstream fout ("lgput.out");
long long n, p, rp, i, j, rf, k;
fin >> n >> p;
rf = 1;
j = 1;
for ( j = 0, rf = 1; (1 << j) <= p; ) {
k = 1;
for (i = 1, rp = n; (1 << i ) <= p - j + 1; i++) {
rp = (rp * rp) % prim;
k = i << i;
}
j += k;
rf = (rf * rp) % prim;
}
fout << rf;
return 0;
}