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
|
def extended_gcd(a, b)
last_remainder, remainder = a.abs, b.abs
x, last_x, y, last_y = 0, 1, 1, 0
while remainder != 0
last_remainder, (quotient, remainder) = remainder, last_remainder.divmod(remainder)
x, last_x = last_x - quotient*x, x
y, last_y = last_y - quotient*y, y
end
return last_remainder, last_x * (a < 0 ? -1 : 1)
end
def invmod(e, et)
g, x = extended_gcd(e, et)
if g != 1
raise 'Multiplicative inverse modulo does not exist!'
end
x % et
end
def chinese_remainder(mods, remainders)
max = mods.inject( :* ) # product of all moduli
series = remainders.zip(mods).map{ |r,m| (r * max * invmod(max/m, m) / m) }
series.inject( :+ ) % max
end
notes = File.readlines('input.txt')[1]
ids = notes.split(',').each_with_index.filter_map do |id, i|
if id != 'x'
[id.to_i, -i % id.to_i]
end
end
moduli = ids.map {|m| m[0]}
remainders = ids.map {|m| m[1]}
puts chinese_remainder(moduli, remainders)
|