From 9e28e4c7b67c54229df11d355047ac8a88ea1817 Mon Sep 17 00:00:00 2001 From: Nguyễn Gia Phong Date: Sun, 15 Dec 2019 15:09:13 +0700 Subject: Normalize pathname --- ntu/luth2.c | 55 +++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 55 insertions(+) create mode 100644 ntu/luth2.c (limited to 'ntu/luth2.c') diff --git a/ntu/luth2.c b/ntu/luth2.c new file mode 100644 index 0000000..46bd99a --- /dev/null +++ b/ntu/luth2.c @@ -0,0 +1,55 @@ +#include + +long long modinv(long a, long b) +{ + /* From: http://rosettacode.org/wiki/Modular_inverse#C */ + + long long t = 0, nt = 1, r = b, nr = a % b, q, tmp; + + while (nr) { + q = r / nr; + + tmp = nt; + nt = t - q * nt; + t = tmp; + + tmp = nr; + nr = r - q * nr; + r = tmp; + } + + return (t < 0) ? t + b : t; +} + +long powmod(long a, long b, long k) +{ + if (b == 1) + return a; + + long long p = powmod(a, b / 2, k); + p = (b % 2) ? p * p * a % k : p * p % k; + + return p; +} + +int main() +{ + short t, i; + long a, b, k, j; + long long c = 1; + + scanf("%hd", &t); + + for (i = t; i; i--) { + scanf("%ld %ld %ld", &a, &b, &k); + + if (b < 0) { + a = modinv(a, k) % k; + b = -b; + } + + printf("%ld\n", (b) ? powmod(a, b, k) : 1); + } + + return 0; +} -- cgit 1.4.1