~quf/computers-are-fast-2020

computers-are-fast-2020/src/13.c -rw-r--r-- 2.2 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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
#include <stdio.h>
#include <limits.h>
#include <ctype.h>
#include <string.h>
#include <errno.h>

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

long long mulmod(unsigned long long a, unsigned long long b, unsigned long long m) {
  /* Returns mod(a*b, c) while avoiding overflow for a*b */
  if (a < (1ULL<<32) && b < (1ULL<<32)) { /* long long is at least 64 bits wide */
    return (a * b) % m;
  }
  unsigned long long ret = 0;
  a = a % m;
  b = b % m;
  for (; b; b >>= 1) {
    if (b & 1) {
      ret = (ret + a) % m;
    }
    a = (a << 1) % m;
  }
  return ret;
}

unsigned long long mod(long long a, long long b) {
  /* assumes b > 0*/
  if (a >= 0) {
    return (unsigned long long) a % b;
  }
  else {
    return (unsigned long long) ((a % b) + b);
  }
}

long long egcd(long long a, long long b, long long *n, long long *m) {
  if (b == 0) {
    *n = 1;
    *m = 0;
    return a;
  }
  else if (abs(a) < abs(b)) {
    return egcd(b, a, m, n);
  }
  long long k = a / b;
  long long r = a - k * b;
  long long tmp;
  long long g = egcd(b, r, &tmp, n);
  *m = tmp - k * (*n);
  return g;
}

int main(void) {
  long earliest;
  scanf("%ld\n", &earliest);
  long part1 = 0;
  long min_wait = LONG_MAX;
  long long part2 = 0;
  long long period = 1;
  long t = 0;
  int c = 0;
  for (int i = 0; (c = getchar()) != EOF;) {
    if (isdigit(c)) {
      t = 10 * t + (c - '0');
    }
    else if ((c == ',' || c == '\n') && t != 0) { /* got our number */
      /* part 1 */
      long rem = t - (earliest % t);
      if (rem < min_wait) {
        min_wait = rem;
        part1 = rem * t;
      }

      /* part 2 */
      long long g, n, m;
      g = egcd(period, t, &n, &m);
      long long d = -(part2 + (long long) i);
      long long k = d / g;
      if (d != k * g) {
        fprintf(stderr, "part2 is not solvable.\n");
        return 1;
      }
      period = t * (period / g);
      /* ((-k * t * m - i) % period) without overflow */
      part2 = mod(mulmod((unsigned long long) t, mulmod(mod(-k, period), mod(m, period), period), period) - i, period);

      t = 0;
      ++i;
    }
    else if (c == 'x') {
      ++i;
    }
  }
  if (ferror(stdin)) {
    fprintf(stderr, "Error: %s\n", strerror(errno));
    return 1;
  }
  printf("%ld\n", part1);
  printf("%lld\n", part2);
  return 0;
}