aboutsummaryrefslogtreecommitdiff
path: root/super_pow.c
blob: 1a68436e99ceb9fe4495d37ef7d5e33c7c4fb3c6 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
// 372. Super Pow
#include "leetcode.h"

/*
 * your task is to calculate `a^b % 1337` where 'a' is a positive integer and
 * 'b' is an extremely large positive integer given in the form of an array
 */

/*
 * the number 1337 only has two divisors: 7 and 191 (excluding 1 and itself), so
 * see if 'a' has a divisor of either of these. also note that 7 and 191 are
 * prime numbers, meaning we can use euler's theorem, or really just fermat's
 * little theorem if the mod 'n' is prime.
 */

int power(int x, int n, int mod) {
  int res = 1;
  for (x %= mod; n; x *= x % mod, n >>= 1)
    if (n & 1)
      res *= x % mod;
  return res;
}

int superPow(int a, int *b, int bSize) {
  if (!(a % 1337))
    return 0;
  int n = 0;
  for (int i = 0; i < bSize; i++)
    n = (n * 10 + b[i]) % 1140;
  if (!n)
    n += 1140;
  return power(a, n, 1337);
}

int main() {
  int b1[] = {3}, b2[] = {1, 0}, b3[] = {4, 3, 3, 8, 5, 2};
  printf("%d\n", superPow(2, b1, ARRAY_SIZE(b1))); // expect: 8
  printf("%d\n", superPow(2, b2, ARRAY_SIZE(b2))); // expect: 1024
  printf("%d\n", superPow(1, b3, ARRAY_SIZE(b3))); // expect: 1
}