ABC 340 F번 복기 - 확장 유클리드 알고리즘 제대로 활용하기

https://atcoder.jp/contests/abc340/tasks/abc340_f F - S = 1 AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 확장 유클리드 알고리즘으로 선형방정식 ax+by = 1의 해를 구하는 전형적인 문제인데... 어설프게 알다보니 해결하지 못했다.. 문제탓?을 하자면 스페셜저지라는 언급을 안해주니.. 여러개 있으면 하나만 출력해도 된다는 언급을 해줘야하는데 그런게 없어서 헷갈리기도.. 문제 핵심은 (x,y)가 주어질때 평면상 (0,0), (x,y), (a,b)이 이루는 삼각형의 넓이가 ..

  • format_list_bulleted Atcoder
  • · 2024. 2. 21.
  • textsms

연분수(continued fraction)를 이용한 선형 디오판토스 방정식의 해를 구하는 방법

1. 연분수 표현에서 a,b의 최대공약수를 바로 구하는 방법 AB의 연분수 표현을 구하고자 한다면, A/B가 기약분수 형태로 들어가줘야한다. 기약분수로 바꿀려면 A,B의 최대공약수가 g = gcd(A,B)일때, pk=A/g,qk=B/g이고 그래서 AB=pkqk이다. 따라서, A/B가 기약분수가 아닐때, 연분수 표현 p,q를 구한 다음 A를 p[-1]로 나눠주면 A,B의 최대공약수가 된다. #A/B가 기약분수가 아닐때, A,B의 최대공약수 구하기 def continued_fraction(p,q): f = [] while q != 0: f.append(p//q) p,q = q,p%q return f def conve..

  • format_list_bulleted 정수론
  • · 2023. 9. 29.
  • textsms

확장된 유클리드 알고리즘(extended euclidean algorithm) 구현해보면서 익히기

1. 베주 항등식(Bézout's Identity) 적어도 하나가 0이 아닌 두 정수 a,b에 대하여 ax+by=gcd(a,b)를 만족하는 정수해 x,y가 반드시 존재한다. 여기서 정수해 x,y는 유일하지 않다. 왜냐하면, 양변에 ab를 더하고 빼보면 ax+ab+by−ab=gcd(a,b)이므로, a(x+b)+b(y−a)=gcd(a,b)이므로, (x,y)가 정수해라면, (x+b,y-a)도 정수해가 된다. 2. 유클리드 알고리즘(Euclidean algorithm) 최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법 (tistory.com) 최대공약수를 빠르게 구하는 알고리즘 - 유클리드 호제법 1. 최대공약수 두 자연수 a,b가 공통으로 가지는 약수중에서 가장 큰..

  • format_list_bulleted 정수론
  • · 2022. 12. 16.
  • textsms