[class3] (백준 6064) 카잉 달력

문제

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다. 

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다. 

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라. 

입력

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

출력

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

제한

예제 입력 1

3
10 12 3 9
10 12 7 2
13 11 5 6

예제 출력 1

33
-1
83

힌트

W3sicHJvYmxlbV9pZCI6IjYwNjQiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWNlNzRcdWM3ODkgXHViMmVjXHViODI1IiwiZGVzY3JpcHRpb24iOiI8cD5cdWNkNWNcdWFkZmNcdWM1ZDAgSUNQQyBcdWQwZDBcdWMwYWNcdWIzMDBcdWIyOTQgXHViMGE4XHVjNTQ0XHViYTU0XHViOWFjXHVjZTc0XHVjNzU4IFx1Yzc4OVx1Y2U3NCBcdWM4MWNcdWFkNmRcdWM3NzQgXHViMTgwXHViNzdjXHVjNmI0IFx1YmIzOFx1YmE4NVx1Yzc0NCBcdWM5YzBcdWIyY2MgXHVjZTc0XHVjNzg5IFx1YzgxY1x1YWQ2ZFx1Yzc0NCBcdWQxYTBcdWIzMDBcdWI4NWMgXHVkNTU4XHVjNWVjIFx1YzEzOFx1YzZjY1x1Yzg0Y1x1YjJlNFx1YjI5NCBcdWMwYWNcdWMyZTRcdWM3NDQgXHViYzFjXHVhY2FjXHVkNTg4XHViMmU0LiBcdWNlNzRcdWM3ODkgXHVjODFjXHVhZDZkXHVjNzU4IFx1YmMzMVx1YzEzMVx1YjRlNFx1Yzc0MCBcdWQyYjlcdWM3NzRcdWQ1NWMgXHViMmVjXHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1YyBcdWFjODNcdWM3M2NcdWI4NWMgXHVjNTRjXHViODI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gXHVhZGY4XHViNGU0XHVjNzQwIE1cdWFjZmMgTlx1YmNmNFx1YjJlNCBcdWM3OTFcdWFjNzBcdWIwOTggXHVhYzE5XHVjNzQwIFx1YjQ1MCBcdWFjMWNcdWM3NTggXHVjNzkwXHVjNWYwXHVjMjE4IHgsIHlcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YWMwMSBcdWIxNDRcdWIzYzRcdWI5N2MgJmx0O3g6eSZndDtcdWM2NDAgXHVhYzE5XHVjNzQwIFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWM2MDBcdWIyZTQuIFx1YWRmOFx1YjRlNFx1Yzc0MCBcdWM3NzQgXHVjMTM4XHVjMGMxXHVjNzU4IFx1YzJkY1x1Y2QwOFx1YzVkMCBcdWQ1NzRcdWIyZjlcdWQ1NThcdWIyOTQgXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWQ1NzRcdWI5N2MgJmx0OzE6MSZndDtcdWI4NWMgXHVkNDVjXHVkNjA0XHVkNTU4XHVhY2UwLCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1ZDU3NFx1Yjk3YyAmbHQ7MjoyJmd0O1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWQ1NThcdWM2MDBcdWIyZTQuICZsdDt4OnkmZ3Q7XHVjNzU4IFx1YjJlNFx1Yzc0YyBcdWQ1NzRcdWI5N2MgXHVkNDVjXHVkNjA0XHVkNTVjIFx1YWM4M1x1Yzc0NCAmbHQ7eCYjMzk7OnkmIzM5OyZndDtcdWM3NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHVjNzkwLiBcdWI5Y2NcdWM3N2MgeCZuYnNwOyZsdDsgTSBcdWM3NzRcdWJhNzQgeCYjMzk7ID0geCArIDFcdWM3NzRcdWFjZTAsIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgeCYjMzk7ID0gMVx1Yzc3NFx1YjJlNC4gXHVhYzE5XHVjNzQwIFx1YmMyOVx1YzJkZFx1YzczY1x1Yjg1YyBcdWI5Y2NcdWM3N2MgeSAmbHQ7IE5cdWM3NzRcdWJhNzQgeSYjMzk7ID0geSArIDFcdWM3NzRcdWFjZTAsIFx1YWRmOFx1YjgwN1x1YzljMCBcdWM1NGFcdWM3M2NcdWJhNzQgeSYjMzk7ID0gMVx1Yzc3NFx1YjJlNC4gJmx0O006TiZndDtcdWM3NDAgXHVhZGY4XHViNGU0IFx1YjJlY1x1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVkNTc0XHViODVjXHVjMTFjLCBcdWM3NzQgXHVkNTc0XHVjNWQwIFx1YzEzOFx1YzBjMVx1Yzc1OCBcdWM4ODVcdWI5ZDBcdWM3NzQgXHViM2M0XHViNzk4XHVkNTVjXHViMmU0XHViMjk0IFx1YzYwOFx1YzViOFx1Yzc3NCBcdWM4MDRcdWQ1NzQgXHVjNjI4XHViMmU0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5cdWM2MDhcdWI5N2MgXHViNGU0XHVjNWI0LCBNID0gMTAgXHVjNzc0XHVhY2UwIE4gPSAxMlx1Yjc3Y1x1YWNlMCBcdWQ1NThcdWM3OTAuIFx1Y2NhYiBcdWJjODhcdWM5ZjggXHVkNTc0XHViMjk0ICZsdDsxOjEmZ3Q7XHViODVjIFx1ZDQ1Y1x1ZDYwNFx1YjQxOFx1YWNlMCwgMTFcdWJjODhcdWM5ZjggXHVkNTc0XHViMjk0ICZsdDsxOjExJmd0O1x1Yjg1YyBcdWQ0NWNcdWQ2MDRcdWI0MWNcdWIyZTQuICZsdDszOjEmZ3Q7XHVjNzQwIDEzXHViYzg4XHVjOWY4IFx1ZDU3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWFjZTAsICZsdDsxMDoxMiZndDtcdWIyOTQgXHViOWM4XHVjOWMwXHViOWM5XHVjNzc4IDYwXHViYzg4XHVjOWY4IFx1ZDU3NFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjhcdWIyZTQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlx1YjEyNCBcdWFjMWNcdWM3NTggXHVjODE1XHVjMjE4IE0sIE4sIHhcdWM2NDAgeVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzggXHViNTRjLCAmbHQ7TTpOJmd0O1x1Yzc3NCBcdWNlNzRcdWM3ODkgXHViMmVjXHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOSBcdWQ1NzRcdWI3N2NcdWFjZTAgXHVkNTU4XHViYTc0ICZsdDt4OnkmZ3Q7XHViMjk0IFx1YmE4NyBcdWJjODhcdWM5ZjggXHVkNTc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NFx1YzljMCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1Yjc3Yy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Yzc4NVx1YjgyNSZuYnNwO1x1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWQ0NWNcdWM5MDAgXHVjNzg1XHViODI1XHVjNzQ0IFx1YzBhY1x1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVjNzg1XHViODI1XHVjNzQwIFRcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1Yjg1YyBcdWFkNmNcdWMxMzFcdWI0MWNcdWIyZTQuIFx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWNjYWIgXHViYzg4XHVjOWY4IFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM3ODVcdWI4MjUgXHViMzcwXHVjNzc0XHVkMTMwXHVjNzU4IFx1YzIxOFx1Yjk3YyBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjODE1XHVjMjE4IFRcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1YjM3MFx1Yzc3NFx1ZDEzMFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1YWQ2Y1x1YzEzMVx1YjQxY1x1YjJlNC4gXHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWIxMjQgXHVhYzFjXHVjNzU4IFx1YzgxNVx1YzIxOCBNLCBOLCB4XHVjNjQwIHlcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IE0sIE4gJmxlOyA0MCwwMDAsIDEgJmxlOyB4ICZsZTsgTSwgMSAmbGU7IHkgJmxlOyBOKSBcdWM1ZWNcdWFlMzBcdWMxMWMgJmx0O006TiZndDtcdWM3NDAgXHVjZTc0XHVjNzg5IFx1YjJlY1x1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVkNTc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiOFx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNkOWNcdWI4MjVcdWM3NDAgXHVkNDVjXHVjOTAwIFx1Y2Q5Y1x1YjgyNVx1Yzc0NCBcdWMwYWNcdWM2YTlcdWQ1NWNcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHViMzcwXHVjNzc0XHVkMTMwXHVjNWQwIFx1YjMwMFx1ZDU3NCwgXHVjODE1XHVjMjE4IGtcdWI5N2MgXHVkNTVjIFx1YzkwNFx1YzVkMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YzVlY1x1YWUzMFx1YzExYyBrXHViMjk0ICZsdDt4OnkmZ3Q7XHVhYzAwIGtcdWJjODhcdWM5ZjggXHVkNTc0XHViOTdjIFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWFjODNcdWM3NDQgXHVjNzU4XHViYmY4XHVkNTVjXHViMmU0LiBcdWI5Y2NcdWM3N2MgJmx0O3g6eSZndDtcdWM1ZDAgXHVjNzU4XHVkNTc0IFx1ZDQ1Y1x1ZDYwNFx1YjQxOFx1YjI5NCBcdWQ1NzRcdWFjMDAgXHVjNWM2XHViMmU0XHViYTc0LCBcdWM5ODksICZsdDt4OnkmZ3Q7XHVhYzAwIFx1YzcyMFx1ZDZhOFx1ZDU1OFx1YzljMCBcdWM1NGFcdWM3NDAgXHVkNDVjXHVkNjA0XHVjNzc0XHViYTc0LCAtMVx1Yzc0NCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiNjA2NCIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkNhaW4gQ2FsZW5kYXIiLCJkZXNjcmlwdGlvbiI6IjxwPkl0IHdhcyByZWNlbnRseSByZXZlYWxlZCBieSB0aGUgSUNQQyBleGNhdmF0aW9uIHRlYW0gdGhhdCB0aGUgSW5jYSBFbXBpcmUgd2FzIGVzdGFibGlzaGVkIGp1c3QgYWZ0ZXIgdGhlIENhaW4gRW1waXJlIHdoaWNoIHdhcyBhIHNwbGVuZGlkIGNpdmlsaXphdGlvbiB0aGF0IGZsb3VyaXNoZWQgaW4gU291dGggQW1lcmljYS4gSXQgaXMgYmVsaWV2ZWQgdGhhdCB0aGUgcGVvcGxlIGluIHRoZSBDYWluIEVtcGlyZSB1c2VkIGFuIGludGVyZXN0aW5nIG9kZCBjYWxlbmRhci4gSW4gdGhlaXIgY2FsZW5kYXIsIGEgeWVhciB3YXMgcmVwcmVzZW50ZWQgYnkgJmx0O3g6eSZndDssIHdoZXJlIHggYW5kIHkgYXJlIG5hdHVyYWwgbnVtYmVycyB3aGljaCBhcmUgbGVzcyB0aGFuIG9yIGVxdWFsIHRvIE0gYW5kIE4sIHJlc3BlY3RpdmVseS4gVGhlIGZpcnN0IHllYXIsIHRoYXQgaXMsIHRoZSBiZWdpbm5pbmcgb2YgdGhlIHdvcmxkIGlzIHJlcHJlc2VudGVkIGJ5ICZsdDsxOjEmZ3Q7LiBUaGUgc2Vjb25kIHllYXIgaXMgcmVwcmVzZW50ZWQgYnkgJmx0OzI6MiZndDsuIExldCAmbHQ7eCYjMzk7OnkmIzM5OyZndDtiZSB0aGUgZm9sbG93aW5nIHllYXIgb2YgJmx0O3g6eSZndDsuIElmIHggJmx0OyBNLCB4JiMzOTsgPSB4ICsgMSwgb3RoZXJ3aXNlIHgmIzM5OyA9IDEuIFNpbWlsYXJseSwgaWYgeSAmbHQ7IE4sIHkmIzM5OyA9IHkgKyAxLCBvdGhlcndpc2UgeSYjMzk7ID0gMS4gVGhlIGxhc3QgeWVhciBvZiB0aGVpciBjYWxlbmRhciBpcyAmbHQ7TTpOJmd0Oy4gSXQgaXMgc2FpZCB0aGF0IHRoZXJlIHdhcyBhIHByb3BoZWN5IHdoaWNoIHN0YXRlcyB0aGUgd29ybGQgZW5kcyBpbiB0aGUgeWVhciAmbHQ7TTpOJmd0Oy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Rm9yIGV4YW1wbGUsIGFzc3VtZSB0aGF0IE0gPSAxMCBhbmQgTiA9IDEyLiBUaGUgZmlyc3QgeWVhciBpcyByZXByZXNlbnRlZCBieSAmbHQ7MToxJmd0Oy4gVGhlIHllYXIgJmx0OzE6MTEmZ3Q7IHJlcHJlc2VudHMgdGhlIDExPHN1cD50aDxcL3N1cD4geWVhciwgJmx0OzM6MSZndDsgcmVwcmVzZW50cyB0aGUgMTM8c3VwPnRoPFwvc3VwPiB5ZWFyLCBhbmQgJmx0OzEwOjEyJmd0OyByZXByZXNlbnRzIHRoZSA2MDxzdXA+dGg8XC9zdXA+IHllYXIgd2hpY2ggaXMgdGhlIGxhc3QgeWVhci4mbmJzcDs8XC9wPlxyXG5cclxuPHA+R2l2ZW4gZm91ciBpbnRlZ2VycyBNLCBOLCB4LCBhbmQgeSwgd3JpdGUgYSBwcm9ncmFtIHRoYXQgY29tcHV0ZXMgdGhlIG51bWJlciBrIHN1Y2ggdGhhdCAmbHQ7eDp5Jmd0OyByZXByZXNlbnRzIHRoZSBrPHN1cD50aDxcL3N1cD4geWVhciwgd2hlcmUgJmx0O3g6eSZndDsgaXMgdGhlIGxhc3QgeWVhciBvZiB0aGUgd29ybGQgaW4gdGhlIENhaW4gQ2FsZW5kYXIuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5Zb3VyIHByb2dyYW0gaXMgdG8gcmVhZCBmcm9tIHN0YW5kYXJkIGlucHV0LiBUaGUgaW5wdXQgY29uc2lzdHMgb2YgVCB0ZXN0IGNhc2VzLiBUaGUgbnVtYmVyIG9mIHRlc3QgY2FzZXMgVCBpcyBnaXZlbiBpbiB0aGUgZmlyc3QgbGluZSBvZiB0aGUgaW5wdXQuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyBmb3VyIGludGVnZXJzIE0sIE4sIHgsIGFuZCB5ICgxICZsZTsgTSxOICZsZTsgNDAgMDAwLCAxICZsZTsgeCAmbGU7IE0sIDEgJmxlOyB5ICZsZTsgTiksIHdoZXJlICZsdDtNOk4mZ3Q7IGlzIHRoZSBsYXN0IHllYXIgb2YgdGhlIHdvcmxkIGluIHRoZSBDYWluIENhbGVuZGFyLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPllvdXIgcHJvZ3JhbSBpcyB0byB3cml0ZSB0byBzdGFuZGFyZCBvdXRwdXQuIFByaW50IGV4YWN0bHkgb25lIGxpbmUgZm9yIGVhY2ggdGVzdCBjYXNlLiBUaGUgbGluZSBzaG91bGQgY29udGFpbiBhbiBpbnRlZ2VyIGssIHdoZXJlIHRoZSBrPHN1cD50aDxcL3N1cD4geWVhciBpcyByZXByZXNlbnRlZCBieSAmbHQ7eDp5Jmd0OyBmb3IgeCBhbmQgeSBnaXZlbiBpbiB0aGUgaW5wdXQuIElmIHRoZXJlIGRvZXNuJnJzcXVvO3QgZXhpc3QgYSB5ZWFyIHJlcHJlc2VudGVkIGJ5ICZsdDt4OnkmZ3Q7LCBwcmludCAtMS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

ICPC > Regionals > Asia Pacific > Korea > Nationwide Internet Competition > Daejeon Nationalwide Internet Competition 2013 B번

• 문제의 오타를 찾은 사람: 2e718, apjw6112, roeniss
• 데이터를 만든 사람: baekjoon

#include <iostream>
using namespace std;

int GCD(int a, int b)
{
    if (a % b == 0)
        return b;
    return GCD(b, a % b);
}

int GetMax(int a, int b)
{
    return a * b / GCD(a, b);
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int tc;
    int input[4];
    cin >> tc;
    while (tc-- > 0)
    {
        cin >> input[0] >> input[1] >> input[2] >> input[3];
        while (1)
        {
            if (input[2] > GetMax(input[0], input[1]) || 
                (input[2] - 1) % input[1] + 1 == input[3])
            {
                break;
            }
            input[2] += input[0];
        }
        if (input[2] > GetMax(input[0], input[1]))
        {
            cout << -1 << '\n';
        }
        else
        {
            cout << input[2] << '\n';
        }
    }
    return 0;
}