Cod sursa(job #1745007)
Utilizator | Adrian Dinu Trixer | Data | 20 august 2016 22:33:16 |
---|---|---|---|
Problema | Ridicare la putere in timp logaritmic | Scor | 0 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.63 kb |
#include <iostream>
#include <fstream>
#define Q 1999999973
using namespace std;
int main()
{
unsigned long long n, p;
// open files
freopen("lgput.in", "r", stdin);
freopen("lgput.out", "w", stdout);
// read input
cin >> n >> p;
// solve
unsigned long long m = 1;
while (p > 1)
{
if (p % 2 == 0)
{
n = (n % Q) * (p % Q);
p /= 2;
}
else
{
m = (m % Q) * (n % Q);
n = (n % Q) * (n % Q);
p = (p - 1) / 2;
}
}
n = (n % Q) * (m % Q);
// write output
cout << n;
return 0;
}