4 ms·
Is this CRT? Not exactly sure, but it does not run for six hours: result = 0 addend = 1 for divisor, desired_offset in [(7, 0), (13, 1), (59, 4),
by Joker_vD 5y ago
Is this CRT? Not exactly sure, but it does not run for six hours:
result = 0
addend = 1
for divisor, desired_offset in [(7, 0), (13, 1), (59, 4), (31, 6), (19, 7)]:
# keep trying numbers until we find the one that, with
# the desired offset added to it, would divide without
# remainder
while (result + desired_offset) % divisor != 0:
result += addend
# adding another addend should not break previous results
# so make it divisible by all previous divisors
addend *= divisor
result %= 7*13*59*31*19 # Is it really needed? Eh.
print(result)