~quf/computers-are-fast-2020

computers-are-fast-2020/src/25.c -rw-r--r-- 1.6 KiB
6f56515eLukas Himbert Draw the rest of the fine owl. 1 year, 7 months ago
                                                                                
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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <stdio.h>
#include <string.h>
#include <errno.h>
#include <limits.h>

#define abs(a) ((a<0)? -a : a)

unsigned long long isqrtceil(unsigned long long n) {
  /* note: this is not very efficient in general; here, it works fine. */
  size_t highest_bit = 0;
  for (; (n >> highest_bit) && highest_bit < CHAR_BIT * sizeof n; ++highest_bit);
  unsigned long long x = 1ULL << (highest_bit >> 2);
  for (; x * x < n; ++x);
  return x;
}

unsigned long long powermod(unsigned long long a, unsigned long long b, unsigned long long p) {
  unsigned long long x = 1;
  for (; b; b >>= 1) {
    if (b & 1) {
      x = (a * x) % p;
    }
    a = (a * a) % p;
  }
  return x;
}

unsigned long long dlog(unsigned long long base, unsigned long long x, unsigned long long p) {
  base %= p;
  x %= p;
  unsigned long long m = isqrtceil(p);
  unsigned long long table[m];
  for (size_t i = 0; i < (size_t) m; ++i) {
    table[i] = powermod(base, i, p);
  }
  unsigned long long b_m_inv = powermod(base, p - m - 1, p);
  for (size_t i = 0; i < (size_t) m; ++i) {
    for (size_t j = 0; j < (size_t) m; ++j) {
      if (x == table[j]) {
        return (unsigned long long) i * m + (unsigned long long) j;
      }
    }
    x = (x * b_m_inv) % p;
  }
  return 0;
}

int main(void) {
  const unsigned long long p = 20201227; // this is prime.
  unsigned long long a, b;
  if (scanf("%llu\n%llu\n", &a, &b) != 2) {
    fprintf(stderr, "Input error: %s\n", strerror(errno));
    return 1;
  }
  if (a < 2 || b < 2) {
    fprintf(stderr, "haha, funny.\n");
    return 1;
  }
  printf("%llu\n", powermod(b, dlog(7, a, p), p));

  return 0;
}