fork(4) download
  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
stdin
939
7,13,x,x,59,x,31,19
stdout
[[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