Cod sursa(job #993593)
Utilizator | Data | 4 septembrie 2013 09:08:59 | |
---|---|---|---|
Problema | Ridicare la putere in timp logaritmic | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.5 kb |
#include <stdio.h>
#define Mod 1999999973
int n;
int pow[32];
long long p;
int main()
{
freopen("lgput.in", "r", stdin);
freopen("lgput.out", "w", stdout);
scanf("%d %d", &n, &p);
pow[0] = n % Mod;
for (int i = 1; i < 32; i++)
pow[i] = ((long long)pow[i-1] * pow[i-1]) % Mod;
int r = 1;
for (int i = 32 - 2; i >= 0; i--)
{
while (p >= ((long long)1 << i))
{
r = ((long long)r * pow[i]) % Mod;
p -= ((long long)1 << i);
}
}
printf("%d\n", r);
return 0;
}