음이 아닌 두 정수 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임을 이용하려고해도 잘 모르겠고..

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