1629번: 곱셈

#include<cstdio>

long long mul(long long a, long long b, long long c);

int main()

{

long long a, b, c;

scanf("%lld %lld %lld", &a, &b, &c);

printf("%lld", mul(a%c, b, c));

}

long long mul(long long a, long long b, long long c)

{

long long ret;

if (b == 0)

return 1;

else if (b % 2 == 1)

return (a*mul(a%c, (b - 1), c)) % c;

else

{

ret = mul(a%c, (b / 2), c) % c;

return (ret*ret)%c;

}

}