fork(4) download
copy 
  1. def ext_gcd(a, b):
  2.     x = 1
  3.     y = 0
  4.     x1 = 0
  5.     y1 = 1
  6.     a1 = a
  7.     b1 = b
  8.  
  9.     while b1 > 0:
  10.         q = a1 // b1
  11.         x, x1 = x1, x - q*x1
  12.         y, y1 = y1, y - q*y1
  13.         a1, b1 = b1, a1 - q*b1
  14.  
  15.     return x, y
  16.  
  17.  
  18. if __name__ == '__main__':
  19.     n = int(input())
  20.     t = input().split(',')
  21.     divs = []
  22.     mx = [-1, -1]
  23.     lcm = 1
  24.     for i in range(len(t)):
  25.         if t[i] == 'x':
  26.             continue
  27.  
  28.         t[i] = int(t[i]) 
  29.  
  30.         k = i
  31.         k %= t[i]
  32.         k = t[i] - k
  33.         k %= t[i]
  34.  
  35.         divs.append([int(t[i]), k])
  36.         lcm *= int(t[i])
  37.         if mx[0] == -1 or divs[-1][0] > mx[0]:
  38.             mx = divs[-1]
  39.  
  40.     print(divs)
  41.  
  42.     while len(divs) > 1:
  43.         n1, a1 = divs[-1]
  44.         n2, a2 = divs[-2]
  45.  
  46.         divs.pop()
  47.         divs.pop()
  48.         m1, m2 = ext_gcd(n1, n2)
  49.         x = a1*m2*n2 + a2*m1*n1
  50.         x %= n1*n2
  51.  
  52.         if x < 0:
  53.             x += n1*n2
  54.         divs.append([n1*n2, x])
  55.         print(divs)
  56.     print(divs[0][1])
Success #stdin #stdout 0.02s 9176KB
comments (?)
stdin
copy 
939
7,13,x,x,59,x,31,19
stdout
copy 
[[7, 0], [13, 12], [59, 55], [31, 25], [19, 12]]
[[7, 0], [13, 12], [59, 55], [589, 335]]
[[7, 0], [13, 12], [34751, 26251]]
[[7, 0], [451763, 165255]]
[[3162341, 1068781]]
1068781
https://ideone.com/5Hyw25
language:
Python 3 (python  3.12)
created:
4 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!