시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 44 22 21 55.263%

문제

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

먼저, 원탁에 모두 앉는다. 총 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+XHJcbiIsImhpbnQiOiI8cD5cdWM2OTRcdWMxMzhcdWQ0NzhcdWMyYTQgXHViYjM4XHVjODFjXHViMjk0Jm5ic3A7PGEgaHJlZj1cImh0dHA6XC9cL3d3dy5hY21pY3BjLm5ldFwvcHJvYmxlbVwvMTE1OFwiPjExNThcdWJjODg8XC9hPlx1Yzc0NCZuYnNwO1x1Y2MzOFx1YWNlMFx1ZDU1OFx1YmE3NCBcdWI0MWNcdWIyZTQuPFwvcD5cclxuIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjY1MjMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJGbGF2aXVzIEpvc2VwaHVzIFJlbG9hZGVkIiwiZGVzY3JpcHRpb24iOiI8cD5GbGF2aXVzIEpvc2VwaHVzIG9uY2Ugd2FzIHRyYXBwZWQgaW4gYSBjYXZlIHRvZ2V0aGVyIHdpdGggaGlzIGNvbXJhZGUgc29sZGllcnMgc3Vycm91bmRlZCBieSBSb21hbnMuIEFsbCBvZiBKb3NlcGh1cyYjMzk7IGZlbGxvdyBzb2xkaWVycyBwcmVmZXJyZWQgbm90IHRvIHN1cnJlbmRlciBidXQgdG8gY29tbWl0IHN1aWNpZGUuIFNvIHRoZXkgYWxsIGZvcm1lZCBhIGNpcmNsZSBhbmQgYWdyZWVkIG9uIGEgbnVtYmVyIGsuIEV2ZXJ5IGstdGggcGVyc29uIGluIHRoZSBjaXJjbGUgd291bGQgdGhlbiBjb21taXQgc3VpY2lkZS4gSG93ZXZlciwgSm9zZXBodXMgaGFkIGRpZmZlcmVudCBwcmlvcml0aWVzIGFuZCBkaWRuJiMzOTt0IHdhbnQgdG8gZGllIGp1c3QgeWV0LiBBY2NvcmRpbmcgdG8gdGhlIGxlZ2VuZCBoZSBtYW5hZ2VkIHRvIGZpbmQgdGhlIHNhZmUgc3BvdCBpbiB0aGUgY2lyY2xlIHdoZXJlIGhlIHdvdWxkIGJlIHRoZSBsYXN0IG9uZSB0byBjb21taXQgc3VpY2lkZS4gSGUgc3VycmVuZGVyZWQgdG8gdGhlIFJvbWFucyBhbmQgYmVjYW1lIGEgY2l0aXplbiBvZiBSb21lIGEgZmV3IHllYXJzIGxhdGVyLjxcL3A+XHJcblxyXG48cD5JdCBpcyBhIGxlc3NlciBrbm93biBmYWN0IHRoYXQgdGhlIHNvdWxzIG9mIEpvc2VwaHVzIGFuZCBoaXMgY29tcmFkZXMgd2VyZSBhbGwgYm9ybiBhZ2FpbiBpbiBtb2Rlcm4gdGltZXMuIE9idmlvdXNseSBKb3NlcGh1cyBhbmQgaGlzIHJlYm9ybiBmZWxsb3cgc29sZGllcnMgd2FudGVkIHRvIGF2b2lkIGEgc2ltaWxhciBmaWFzY28gaW4gdGhlIGZ1dHVyZS4gVGh1cyB0aGV5IGFza2VkIGEgY29uc3VsdGluZyBjb21wYW55IHRvIHdvcmsgb3V0IGEgYmV0dGVyIGRlY2lzaW9uIHNjaGVtZS4gVGhlIGNvbXBhbnkgY2FtZSB1cCB3aXRoIHRoZSBmb2xsb3dpbmcgc2NoZW1lOjxcL3A+XHJcblxyXG48dWw+XHJcblx0PGxpPkZvciB0aGUgc2FrZSBvZiB0cmFkaXRpb24gYWxsIHNvbGRpZXJzIHNob3VsZCBzdGFuZCBpbiBhIGNpcmNsZS4gVGhpcyB3YXkgYSBudW1iZXIgYmV0d2VlbiAwIGFuZCBOLTEgaXMgYXNzaWduZWQgdG8gZWFjaCBzb2xkaWVyLCB3aGVyZSBOIGlzIHRoZSBudW1iZXIgb2Ygc29sZGllcnMuPFwvbGk+XHJcblx0PGxpPkFzIGNoYW5naW5nIG51bWJlcnMgaW4gdGhlIG9sZCBzY2hlbWUgdHVybmVkIG91dCB0byBiZSBob3JyaWJseSBpbmVmZmljaWVudCwgdGhlIG51bWJlciBhc3NpZ25lZCB0byBhIHNvbGRpZXIgd2lsbCBub3QgY2hhbmdlIHRocm91Z2hvdXQgdGhlIGdhbWUuPFwvbGk+XHJcblx0PGxpPlRoZSBjb25zdWx0aW5nIGNvbXBhbnkgd2lsbCBwcm92aWRlIHR3byBudW1iZXJzIGEgYW5kIGIgd2hpY2ggd2lsbCBiZSB1c2VkIHRvIGNhbGN1bGF0ZSB0aGUgbnVtYmVyIG9mIHRoZSBuZXh0IHNvbGRpZXIgYXMgZm9sbG93czogTGV0IHggYmUgdGhlIG51bWJlciBvZiB0aGUgY3VycmVudCBzb2xkaWVyLCB0aGVuIHRoZSBudW1iZXIgb2YgdGhlIG5leHQgc29sZGllciBpcyB0aGUgcmVtYWluZGVyIG9mIGEmbWlkZG90O3gyICsgYiBtb2QgTi48XC9saT5cclxuXHQ8bGk+V2Ugc3RhcnQgd2l0aCB0aGUgc29sZGllciB3aXRoIG51bWJlciAwIGFuZCBlYWNoIHNvbGRpZXIgY2FsY3VsYXRlcyB0aGUgbnVtYmVyIG9mIHRoZSBuZXh0IHNvbGRpZXIgYWNjb3JkaW5nIHRvIHRoZSBmb3JtdWxhIGFib3ZlLjxcL2xpPlxyXG5cdDxsaT5BcyBldmVyeW9uZSBkZXNlcnZlcyBhIHNlY29uZCBjaGFuY2UgYSBzb2xkaWVyIHdpbGwgY29tbWl0IHN1aWNpZGUgb25jZSBoaXMgbnVtYmVyIGlzIGNhbGN1bGF0ZWQgZm9yIHRoZSBzZWNvbmQgdGltZS48XC9saT5cclxuXHQ8bGk+SW4gdGhlIGV2ZW50IHRoYXQgdGhlIG51bWJlciBvZiBhIHNvbGRpZXIgaXMgY2FsY3VsYXRlZCBmb3IgdGhlIHRoaXJkIHRpbWUgdGhlIGdhbWUgd2lsbCBlbmQgYW5kIGFsbCByZW1haW5pbmcgc29sZGllcnMgd2lsbCBzdXJyZW5kZXIuPFwvbGk+XHJcbjxcL3VsPlxyXG5cclxuPHA+WW91IGFyZSB0byB3cml0ZSBhIHByb2dyYW0gdGhhdCBnaXZlbiB0aGUgbnVtYmVyIG9mIHNvbGRpZXJzIE4gYW5kIHRoZSBjb25zdGFudHMgYSBhbmQgYiBkZXRlcm1pbmVzIHRoZSBudW1iZXIgb2Ygc3Vydml2b3JzPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgaW5wdXQgZmlsZSBjb25zaXN0cyBvZiBzZXZlcmFsIHRlc3QgY2FzZXMuIEVhY2ggdGVzdCBjYXNlIGNvbnNpc3RzIG9mIGEgc2luZ2xlIGxpbmUgY29udGFpbmluZyB0aGUgdGhyZWUgaW50ZWdlcnMgTiAoMiAmbGU7IE4gJmxlOyAxMDxzdXA+OTxcL3N1cD4pLCBhIGFuZCBiICgwICZsZTsgYSxiICZsdDsgTikgc2VwYXJhdGVkIGJ5IHdoaXRlIHNwYWNlLiBZb3UgbWF5IHNhZmVseSBhc3N1bWUgdGhhdCB0aGUgZmlyc3Qgc29sZGllciBkaWVzIGFmdGVyIG5vIG1vcmUgdGhhbiBvbmUgbWlsbGlvbiAoMTA8c3VwPjY8XC9zdXA+KSBzdGVwcy4gVGhlIGlucHV0IGlzIHRlcm1pbmF0ZWQgYnkgYSBzaW5nbGUgbnVtYmVyIDAgd2hpY2ggc2hvdWxkIG5vdCBiZSBwcm9jZXNzZWQ8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggdGVzdCBjYXNlIG91dHB1dCBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIG51bWJlciBvZiBzb2xkaWVycyB0aGF0IHN1cnZpdmUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=