Advertisement
Kirizhik

Untitled

May 19th, 2019
87
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Python 0.51 KB | None | 0 0
  1. from math import gcd,
  2. def rev(a, m):
  3.     if a == 1:
  4.         return 1
  5.     return (1 - rev(m % a, a) * m) / a + m
  6. def lcm(a,b):
  7.     return (a * b) // gcd(a, b)
  8. def solve_x(a1,m1,a2,m2):
  9.     g = gcd(m1, m2)
  10.     k = (a2 - a1) / g * rev(m1/g, m2/g) %  (m2/g)
  11.     return a1 + k * m1
  12. n = int(input())
  13. a = [(int(input()), i + 2) for i in range(n)]
  14. new_x = solve_x(*a[0],*a[1])
  15. lc = lcm(a[0][1],a[1][1])
  16. for i in range(2,len(a)):
  17.     new_x = solve_x(new_x,lc,*a[i])
  18.     lc = lcm(a[i][1],lc)
  19. print(new_x)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement