2020/day13.c

   1 #include <stdio.h>
   2 #include <stdlib.h>
   3 #include <limits.h>
   4 #include <assert.h>
   5
   6 long mul(long a, long b, long m) {
   7   long d = 0, mp2 = m >> 1;
   8   int i;
   9   if (a < 0)
  10     a += m;
  11   if (b < 0)
  12     b += m;
  13   assert(m < 0x4000000000000000ULL);
  14   assert(a < m && b < m);
  15   for (i = 0; i < 63; i++) {
  16     d = (d > mp2) ? (d << 1) - m : d << 1;
  17     if (a & 0x4000000000000000ULL) d += b;
  18     if (d >= m) d -= m;
  19     a <<= 1;
  20   }
  21   return d;
  22 }
  23 void ext(int a, int b, int *m, int *n) {
  24   int old_r = a, r = b;
  25   int old_s = 1, s = 0;
  26   int old_t = 0, t = 1;
  27   int tmp;
  28   while (r) {
  29     int q = old_r / r;
  30     tmp = r;
  31     r = old_r - q * r;
  32     old_r = tmp;
  33     tmp = s;
  34     s = old_s - q * s;
  35     old_s = tmp;
  36     tmp = t;
  37     t = old_t - q * t;
  38     old_t = tmp;
  39   }
  40   *m = old_s;
  41   *n = old_t;
  42 }
  43 int main() {
  44   int time, best, i, n = 0, idx = 0;
  45   char c[5];
  46   int num[10], rem[10];
  47   int prod1 = 1, prod2 = 1, m;
  48   int rem1 = 0, rem2 = 0;
  49   long res;
  50   scanf("%d ", &time);
  51   best = time;
  52   while (scanf("%[x0123456789],", c) > 0) {
  53     n++;
  54     if (*c == 'x')
  55       continue;
  56     i = atoi(c);
  57     if ((i - time % i) < (best - time % best))
  58       best = i;
  59     num[idx] = i;
  60     rem[idx] = (5 * i - n + 1) % i;
  61     idx++;
  62   }
  63   for (i = 0; i < idx; i++) {
  64     int *p = prod2 < prod1 ? &prod2 : &prod1;
  65     int *r = prod2 < prod1 ? &rem2 : &rem1;
  66     if (*p == 1) {
  67       *p = num[i];
  68       *r = rem[i];
  69     } else {
  70       ext(*p, num[i], &m, &n);
  71       *r = (mul(mul(*r, n, *p * num[i]), num[i], *p * num[i]) +
  72             mul(mul(rem[i], m, *p * num[i]), *p, *p * num[i])) % (*p * num[i]);
  73       *p *= num[i];
  74     }
  75   }
  76   ext(prod1, prod2, &m, &n);
  77   res = mul(mul(rem1, n, 1L * prod1 * prod2), prod2, 1L * prod1 * prod2) +
  78     mul(mul(rem2, m, 1L * prod1 * prod2), prod1, 1L * prod1 * prod2);
  79   printf("%d %ld\n", (best - time % best) * best, res);
  80   return 0;
  81 }