시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 128 MB3071338240.196%

문제

프로 드링커 상근이는 술을 마실때, 요세푸스 문제와 같은 순서로 술을 마신다. 요세푸스 문제를 천 번 넘게 푼 상근이는 머리 속으로 가장 마지막에 술을 마시는 사람의 위치를 계산할 수 있다. 따라서, 같이 술을 마시는 친구들은 상근이를 이기기 위해서 술을 마시는 새로운 순서를 제시했다.

먼저, 원탁에 모두 앉는다. 총 N명이 원탁에 앉았다면, 각 사람의 번호는 0번부터 N-1번이 된다.

요세푸스 문제와 다르게 다음 사람을 고르기 위해서 두 숫자 a와 b를 이용한다. 현재 선택된 사람의 번호가 x라면, 다음 사람의 번호는 ax2+b mod N이 된다.

가장 처음 시작하는 사람의 번호는 0번이다. 다음 사람의 번호는 위의 식을 이용해서 고른다.

각 사람은 한 번의 기회를 더 받을 수 있다. 즉, 한 번 걸리면 술을 마시는 것이 아니고, 두 번 걸렸을 때, 술을 마시는 것이다.

만약, 어떤 사람이 세 번 걸렸다면, 그 즉시 모두 자리를 박차고 일어나 집으로 간다.

N과 a, b가 주어졌을 때, 술을 마시지 않고 집으로 가는 사람의 수를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있으며, 세 숫자 N, a, b가 공백으로 구분되어져 있다. (2 ≤ N ≤ 109, 0 ≤ a, b < N) 또, 첫 사람이 술을 마시기 위해 필요한 단계의 수는 106보다 작다. 입력의 마지막 줄에는 0이 하나 주어진다.

출력

각 테스트 케이스에 대해서, 술을 마시지 않고 집으로 가는 사람의 수를 출력한다.

예제 입력 1

2 1 1
5 1 1
10 3 7
101 9 2
698253463 1 181945480
1000000000 999999999 999999999
0

예제 출력 1

0
2
4
96
698177783
999999994

힌트

요세푸스 문제는 1158번을 참고하면 된다.

W3sicHJvYmxlbV9pZCI6IjY1MjMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM2OTRcdWMxMzhcdWQ0NzhcdWMyYTQgXHVkNTVjIFx1YmM4OCBcdWIzNTQhIiwiZGVzY3JpcHRpb24iOiI8cD5cdWQ1MDRcdWI4NWMgXHViNGRjXHViOWMxXHVjZWU0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YjI5NCBcdWMyMjBcdWM3NDQgXHViOWM4XHVjMmU0XHViNTRjLCBcdWM2OTRcdWMxMzhcdWQ0NzhcdWMyYTQgXHViYjM4XHVjODFjXHVjNjQwIFx1YWMxOVx1Yzc0MCBcdWMyMWNcdWMxMWNcdWI4NWMgXHVjMjIwXHVjNzQ0IFx1YjljOFx1YzJlMFx1YjJlNC4gXHVjNjk0XHVjMTM4XHVkNDc4XHVjMmE0IFx1YmIzOFx1YzgxY1x1Yjk3YyBcdWNjOWMgXHViYzg4IFx1YjExOFx1YWM4YyBcdWQ0N2MgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YmEzOFx1YjlhYyBcdWMxOGRcdWM3M2NcdWI4NWMgXHVhYzAwXHVjN2E1IFx1YjljOFx1YzljMFx1YjljOVx1YzVkMCBcdWMyMjBcdWM3NDQgXHViOWM4XHVjMmRjXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWM3MDRcdWNlNThcdWI5N2MgXHVhY2M0XHVjMGIwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVhYzE5XHVjNzc0IFx1YzIyMFx1Yzc0NCBcdWI5YzhcdWMyZGNcdWIyOTQgXHVjZTVjXHVhZDZjXHViNGU0XHVjNzQwIFx1YzBjMVx1YWRmY1x1Yzc3NFx1Yjk3YyBcdWM3NzRcdWFlMzBcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YzIyMFx1Yzc0NCBcdWI5YzhcdWMyZGNcdWIyOTQgXHVjMGM4XHViODVjXHVjNmI0IFx1YzIxY1x1YzExY1x1Yjk3YyBcdWM4MWNcdWMyZGNcdWQ1ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YmEzY1x1YzgwMCwgXHVjNmQwXHVkMGMxXHVjNWQwIFx1YmFhOFx1YjQ1MCBcdWM1NDlcdWIyOTRcdWIyZTQuIFx1Y2QxZCBOXHViYTg1XHVjNzc0IFx1YzZkMFx1ZDBjMVx1YzVkMCBcdWM1NDlcdWM1NThcdWIyZTRcdWJhNzQsIFx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IDBcdWJjODhcdWJkODBcdWQxMzAgTi0xXHViYzg4XHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjNjk0XHVjMTM4XHVkNDc4XHVjMmE0IFx1YmIzOFx1YzgxY1x1YzY0MCBcdWIyZTRcdWI5NzRcdWFjOGMgXHViMmU0XHVjNzRjIFx1YzBhY1x1Yjc4Y1x1Yzc0NCBcdWFjZTBcdWI5NzRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1YjQ1MCBcdWMyMmJcdWM3OTAgYVx1YzY0MCBiXHViOTdjIFx1Yzc3NFx1YzZhOVx1ZDU1Y1x1YjJlNC4gXHVkNjA0XHVjN2FjIFx1YzEyMFx1ZDBkZFx1YjQxYyBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzg4XHVkNjM4XHVhYzAwIHhcdWI3N2NcdWJhNzQsIFx1YjJlNFx1Yzc0YyBcdWMwYWNcdWI3OGNcdWM3NTggXHViYzg4XHVkNjM4XHViMjk0IGF4PHN1cD4yPFwvc3VwPitiIG1vZCBOXHVjNzc0IFx1YjQxY1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAwXHVjN2E1IFx1Y2M5OFx1Yzc0YyBcdWMyZGNcdWM3OTFcdWQ1NThcdWIyOTQgXHVjMGFjXHViNzhjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAwXHViYzg4XHVjNzc0XHViMmU0LiBcdWIyZTRcdWM3NGMgXHVjMGFjXHViNzhjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCBcdWM3MDRcdWM3NTggXHVjMmRkXHVjNzQ0IFx1Yzc3NFx1YzZhOVx1ZDU3NFx1YzExYyBcdWFjZTBcdWI5NzhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWMwYWNcdWI3OGNcdWM3NDAgXHVkNTVjIFx1YmM4OFx1Yzc1OCBcdWFlMzBcdWQ2OGNcdWI5N2MgXHViMzU0IFx1YmMxYlx1Yzc0NCBcdWMyMTggXHVjNzg4XHViMmU0LiBcdWM5ODksIFx1ZDU1YyBcdWJjODggXHVhYzc4XHViOWFjXHViYTc0IFx1YzIyMFx1Yzc0NCBcdWI5YzhcdWMyZGNcdWIyOTQgXHVhYzgzXHVjNzc0IFx1YzU0NFx1YjJjOFx1YWNlMCwgXHViNDUwIFx1YmM4OCBcdWFjNzhcdWI4MzhcdWM3NDQgXHViNTRjLCBcdWMyMjBcdWM3NDQgXHViOWM4XHVjMmRjXHViMjk0IFx1YWM4M1x1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHViOWNjXHVjNTdkLCBcdWM1YjRcdWI1YTQgXHVjMGFjXHViNzhjXHVjNzc0IFx1YzEzOCBcdWJjODggXHVhYzc4XHViODM4XHViMmU0XHViYTc0LCBcdWFkZjggXHVjOTg5XHVjMmRjIFx1YmFhOFx1YjQ1MCBcdWM3OTBcdWI5YWNcdWI5N2MgXHViYzE1XHVjYzI4XHVhY2UwIFx1Yzc3Y1x1YzViNFx1YjA5OCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVhYzA0XHViMmU0LjxcL3A+XHJcblxyXG48cD5OXHVhY2ZjIGEsIGJcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjMjIwXHVjNzQ0IFx1YjljOFx1YzJkY1x1YzljMCBcdWM1NGFcdWFjZTAgXHVjOWQxXHVjNzNjXHViODVjIFx1YWMwMFx1YjI5NCBcdWMwYWNcdWI3OGNcdWM3NTggXHVjMjE4XHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHViMmU0LiBcdWFjMDEgXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1YjI5NCBcdWQ1NWMgXHVjOTA0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1YzEzOCBcdWMyMmJcdWM3OTAgTiwgYSwgYlx1YWMwMCBcdWFjZjVcdWJjMzFcdWM3M2NcdWI4NWMgXHVhZDZjXHViZDg0XHViNDE4XHVjNWI0XHVjODM4IFx1Yzc4OFx1YjJlNC4gKDIgJmxlOyBOICZsZTsgMTA8c3VwPjk8XC9zdXA+LCAwICZsZTsgYSwgYiAmbHQ7IE4pIFx1YjYxMCwgXHVjY2FiIFx1YzBhY1x1Yjc4Y1x1Yzc3NCBcdWMyMjBcdWM3NDQgXHViOWM4XHVjMmRjXHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWQ1NDRcdWM2OTRcdWQ1NWMgXHViMmU4XHVhY2M0XHVjNzU4IFx1YzIxOFx1YjI5NCAxMDxzdXA+NjxcL3N1cD5cdWJjZjRcdWIyZTQgXHVjNzkxXHViMmU0LiBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAwXHVjNzc0IFx1ZDU1OFx1YjA5OCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWMyMjBcdWM3NDQgXHViOWM4XHVjMmRjXHVjOWMwIFx1YzU0YVx1YWNlMCBcdWM5ZDFcdWM3M2NcdWI4NWMgXHVhYzAwXHViMjk0IFx1YzBhY1x1Yjc4Y1x1Yzc1OCBcdWMyMThcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiI8cD5cdWM2OTRcdWMxMzhcdWQ0NzhcdWMyYTQgXHViYjM4XHVjODFjXHViMjk0Jm5ic3A7PGEgaHJlZj1cImh0dHA6XC9cL3d3dy5hY21pY3BjLm5ldFwvcHJvYmxlbVwvMTE1OFwiPjExNThcdWJjODg8XC9hPlx1Yzc0NCZuYnNwO1x1Y2MzOFx1YWNlMFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI2NTIzIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiRmxhdml1cyBKb3NlcGh1cyBSZWxvYWRlZCIsImRlc2NyaXB0aW9uIjoiPHA+Rmxhdml1cyBKb3NlcGh1cyBvbmNlIHdhcyB0cmFwcGVkIGluIGEgY2F2ZSB0b2dldGhlciB3aXRoIGhpcyBjb21yYWRlIHNvbGRpZXJzIHN1cnJvdW5kZWQgYnkgUm9tYW5zLiBBbGwgb2YgSm9zZXBodXMmIzM5OyBmZWxsb3cgc29sZGllcnMgcHJlZmVycmVkIG5vdCB0byBzdXJyZW5kZXIgYnV0IHRvIGNvbW1pdCBzdWljaWRlLiBTbyB0aGV5IGFsbCBmb3JtZWQgYSBjaXJjbGUgYW5kIGFncmVlZCBvbiBhIG51bWJlciBrLiBFdmVyeSBrLXRoIHBlcnNvbiBpbiB0aGUgY2lyY2xlIHdvdWxkIHRoZW4gY29tbWl0IHN1aWNpZGUuIEhvd2V2ZXIsIEpvc2VwaHVzIGhhZCBkaWZmZXJlbnQgcHJpb3JpdGllcyBhbmQgZGlkbiYjMzk7dCB3YW50IHRvIGRpZSBqdXN0IHlldC4gQWNjb3JkaW5nIHRvIHRoZSBsZWdlbmQgaGUgbWFuYWdlZCB0byBmaW5kIHRoZSBzYWZlIHNwb3QgaW4gdGhlIGNpcmNsZSB3aGVyZSBoZSB3b3VsZCBiZSB0aGUgbGFzdCBvbmUgdG8gY29tbWl0IHN1aWNpZGUuIEhlIHN1cnJlbmRlcmVkIHRvIHRoZSBSb21hbnMgYW5kIGJlY2FtZSBhIGNpdGl6ZW4gb2YgUm9tZSBhIGZldyB5ZWFycyBsYXRlci48XC9wPlxyXG5cclxuPHA+SXQgaXMgYSBsZXNzZXIga25vd24gZmFjdCB0aGF0IHRoZSBzb3VscyBvZiBKb3NlcGh1cyBhbmQgaGlzIGNvbXJhZGVzIHdlcmUgYWxsIGJvcm4gYWdhaW4gaW4gbW9kZXJuIHRpbWVzLiBPYnZpb3VzbHkgSm9zZXBodXMgYW5kIGhpcyByZWJvcm4gZmVsbG93IHNvbGRpZXJzIHdhbnRlZCB0byBhdm9pZCBhIHNpbWlsYXIgZmlhc2NvIGluIHRoZSBmdXR1cmUuIFRodXMgdGhleSBhc2tlZCBhIGNvbnN1bHRpbmcgY29tcGFueSB0byB3b3JrIG91dCBhIGJldHRlciBkZWNpc2lvbiBzY2hlbWUuIFRoZSBjb21wYW55IGNhbWUgdXAgd2l0aCB0aGUgZm9sbG93aW5nIHNjaGVtZTo8XC9wPlxyXG5cclxuPHVsPlxyXG5cdDxsaT5Gb3IgdGhlIHNha2Ugb2YgdHJhZGl0aW9uIGFsbCBzb2xkaWVycyBzaG91bGQgc3RhbmQgaW4gYSBjaXJjbGUuIFRoaXMgd2F5IGEgbnVtYmVyIGJldHdlZW4gMCBhbmQgTi0xIGlzIGFzc2lnbmVkIHRvIGVhY2ggc29sZGllciwgd2hlcmUgTiBpcyB0aGUgbnVtYmVyIG9mIHNvbGRpZXJzLjxcL2xpPlxyXG5cdDxsaT5BcyBjaGFuZ2luZyBudW1iZXJzIGluIHRoZSBvbGQgc2NoZW1lIHR1cm5lZCBvdXQgdG8gYmUgaG9ycmlibHkgaW5lZmZpY2llbnQsIHRoZSBudW1iZXIgYXNzaWduZWQgdG8gYSBzb2xkaWVyIHdpbGwgbm90IGNoYW5nZSB0aHJvdWdob3V0IHRoZSBnYW1lLjxcL2xpPlxyXG5cdDxsaT5UaGUgY29uc3VsdGluZyBjb21wYW55IHdpbGwgcHJvdmlkZSB0d28gbnVtYmVycyBhIGFuZCBiIHdoaWNoIHdpbGwgYmUgdXNlZCB0byBjYWxjdWxhdGUgdGhlIG51bWJlciBvZiB0aGUgbmV4dCBzb2xkaWVyIGFzIGZvbGxvd3M6IExldCB4IGJlIHRoZSBudW1iZXIgb2YgdGhlIGN1cnJlbnQgc29sZGllciwgdGhlbiB0aGUgbnVtYmVyIG9mIHRoZSBuZXh0IHNvbGRpZXIgaXMgdGhlIHJlbWFpbmRlciBvZiBhJm1pZGRvdDt4MiArIGIgbW9kIE4uPFwvbGk+XHJcblx0PGxpPldlIHN0YXJ0IHdpdGggdGhlIHNvbGRpZXIgd2l0aCBudW1iZXIgMCBhbmQgZWFjaCBzb2xkaWVyIGNhbGN1bGF0ZXMgdGhlIG51bWJlciBvZiB0aGUgbmV4dCBzb2xkaWVyIGFjY29yZGluZyB0byB0aGUgZm9ybXVsYSBhYm92ZS48XC9saT5cclxuXHQ8bGk+QXMgZXZlcnlvbmUgZGVzZXJ2ZXMgYSBzZWNvbmQgY2hhbmNlIGEgc29sZGllciB3aWxsIGNvbW1pdCBzdWljaWRlIG9uY2UgaGlzIG51bWJlciBpcyBjYWxjdWxhdGVkIGZvciB0aGUgc2Vjb25kIHRpbWUuPFwvbGk+XHJcblx0PGxpPkluIHRoZSBldmVudCB0aGF0IHRoZSBudW1iZXIgb2YgYSBzb2xkaWVyIGlzIGNhbGN1bGF0ZWQgZm9yIHRoZSB0aGlyZCB0aW1lIHRoZSBnYW1lIHdpbGwgZW5kIGFuZCBhbGwgcmVtYWluaW5nIHNvbGRpZXJzIHdpbGwgc3VycmVuZGVyLjxcL2xpPlxyXG48XC91bD5cclxuXHJcbjxwPllvdSBhcmUgdG8gd3JpdGUgYSBwcm9ncmFtIHRoYXQgZ2l2ZW4gdGhlIG51bWJlciBvZiBzb2xkaWVycyBOIGFuZCB0aGUgY29uc3RhbnRzIGEgYW5kIGIgZGV0ZXJtaW5lcyB0aGUgbnVtYmVyIG9mIHN1cnZpdm9yczxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGlucHV0IGZpbGUgY29uc2lzdHMgb2Ygc2V2ZXJhbCB0ZXN0IGNhc2VzLiBFYWNoIHRlc3QgY2FzZSBjb25zaXN0cyBvZiBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIHRocmVlIGludGVnZXJzIE4gKDIgJmxlOyBOICZsZTsgMTA8c3VwPjk8XC9zdXA+KSwgYSBhbmQgYiAoMCAmbGU7IGEsYiAmbHQ7IE4pIHNlcGFyYXRlZCBieSB3aGl0ZSBzcGFjZS4gWW91IG1heSBzYWZlbHkgYXNzdW1lIHRoYXQgdGhlIGZpcnN0IHNvbGRpZXIgZGllcyBhZnRlciBubyBtb3JlIHRoYW4gb25lIG1pbGxpb24gKDEwPHN1cD42PFwvc3VwPikgc3RlcHMuIFRoZSBpbnB1dCBpcyB0ZXJtaW5hdGVkIGJ5IGEgc2luZ2xlIG51bWJlciAwIHdoaWNoIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkPFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHRlc3QgY2FzZSBvdXRwdXQgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBudW1iZXIgb2Ygc29sZGllcnMgdGhhdCBzdXJ2aXZlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IkVuZ2xpc2gifV0=