appa   2년 전

음이 아닌 두 정수 a, b가 주어졌을 때, a+=b, b+=a 두 개의 연산으로 다른 정수 s를 만들 수 있는지 여부를 판단하는 문제에요.

저는 2개의 pair로 상태를 표현했을 때(예를 들어 a = (1,0), b = (0,1), a+2b = (1,2)와 같이), a와 b앞에 있을 수 있는 수와 피보나치 수와 연관이 있는 것 같아서 머리를 굴려보는데.. 잘 모르겠네요ㅠㅠ

a,b,s가 10^18이하인 수라서 막막합니다.

일차부정방정식 ax+by=c에서 d=gcd(a,b)라 할 때, 이 방정식이 정수해를 갖기 위한 필요충분조건은 d|c임을 이용하려고해도 잘 모르겠고..

혹시 떠오르는 아이디어나 풀이가 생각나시면 댓글 부탁드려요~

WeissBlume   2년 전

Ax + By = S 를 만족하고 x>0, y>0 이며 gcd(x,y) = 1인 x와 y가 존재할 때 확실히 답이 존재하는 것 같은데.. 빠르게 하는 방법을 모르겠네요 ㅠㅠ

댓글을 작성하려면 로그인해야 합니다.