시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB113848335940.749%

문제

도현이는 수학 숙제를 하고 있다. 문제는 다음과 같다.

다음과 같이 재귀적으로 정의된 수열이 있다.

\(x_0 = 1\)

\(x_i = x_{\lfloor i - \sqrt{i} \rfloor} + x_{\lfloor \ln{(i)} \rfloor} + x_{\lfloor i \sin^{2}{(i)} \rfloor}\)

이때, \(x_{1000000}\)을 구하시오.

\(i\)가 주어졌을 때, \(x_i\)를 구하는 프로그램을 작성하시오.

입력

입력은 여러 개의 테스트 케이스로 이루어져 있으며, 한 줄에 하나씩 주어진다.

각 줄에는 \(i\)가 주어지며, 이 수는 0보다 작지 않고, 백만보다 크지 않다.

입력의 마지막 줄에는 -1이 주어지며, 이 수는 입력의 마지막을 나타내는 수이다.

출력

입력으로 주어진 \(i\)마다 \(x_i\)를 1000000로 나눈 나머지를 출력한다.

예제 입력 1

0
-1

예제 출력 1

1
W3sicHJvYmxlbV9pZCI6IjQxNzIiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJzcXJ0IGxvZyBzaW4iLCJkZXNjcmlwdGlvbiI6IjxwPlx1YjNjNFx1ZDYwNFx1Yzc3NFx1YjI5NCBcdWMyMThcdWQ1NTkgXHVjMjE5XHVjODFjXHViOTdjIFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTQuIFx1YmIzOFx1YzgxY1x1YjI5NCBcdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHViMmU0LjxcL3A+XHJcblxyXG48YmxvY2txdW90ZT5cclxuPHA+XHViMmU0XHVjNzRjXHVhY2ZjIFx1YWMxOVx1Yzc3NCBcdWM3YWNcdWFkYzBcdWM4MDFcdWM3M2NcdWI4NWMgXHVjODE1XHVjNzU4XHViNDFjIFx1YzIxOFx1YzVmNFx1Yzc3NCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxcKHhfMCA9IDFcXCk8XC9wPlxyXG5cclxuPHA+XFwoeF9pID0geF97XFxsZmxvb3IgaSAtIFxcc3FydHtpfSBcXHJmbG9vcn0gKyB4X3tcXGxmbG9vciBcXGxueyhpKX0gXFxyZmxvb3J9ICsgeF97XFxsZmxvb3IgaSBcXHNpbl57Mn17KGkpfSBcXHJmbG9vcn1cXCk8XC9wPlxyXG5cclxuPHA+XHVjNzc0XHViNTRjLCBcXCh4X3sxMDAwMDAwfVxcKVx1Yzc0NCBcdWFkNmNcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuPFwvYmxvY2txdW90ZT5cclxuXHJcbjxwPlxcKGlcXClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXFwoeF9pXFwpXHViOTdjIFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzQwIFx1YzVlY1x1YjdlYyBcdWFjMWNcdWM3NTggXHVkMTRjXHVjMmE0XHVkMmI4IFx1Y2YwMFx1Yzc3NFx1YzJhNFx1Yjg1YyBcdWM3NzRcdWI4ZThcdWM1YjRcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWQ1NWMgXHVjOTA0XHVjNWQwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMSBcdWM5MDRcdWM1ZDBcdWIyOTQmbmJzcDtcXChpXFwpXHVhYzAwIFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YzIxOFx1YjI5NCAwXHViY2Y0XHViMmU0IFx1Yzc5MVx1YzljMCBcdWM1NGFcdWFjZTAsIFx1YmMzMVx1YjljY1x1YmNmNFx1YjJlNCBcdWQwNmNcdWM5YzAgXHVjNTRhXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5IFx1YzkwNFx1YzVkMFx1YjI5NCAtMVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NCBcdWMyMThcdWIyOTQgXHVjNzg1XHViODI1XHVjNzU4IFx1YjljOFx1YzljMFx1YjljOVx1Yzc0NCBcdWIwOThcdWQwYzBcdWIwYjRcdWIyOTQgXHVjMjE4XHVjNzc0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlx1Yzc4NVx1YjgyNVx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzQgXFwoaVxcKVx1YjljOFx1YjJlNCBcXCh4X2lcXClcdWI5N2MgMTAwMDAwMFx1Yjg1YyBcdWIwOThcdWIyMDggXHViMDk4XHViYTM4XHVjOWMwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJLb3JlYW4ifSx7InByb2JsZW1faWQiOiI0MTcyIiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoic3FydCBsb2cgc2luIiwiZGVzY3JpcHRpb24iOiI8cD5BbiBldmlsIHByb2Zlc3NvciBoYXMganVzdCBhc3NpZ25lZCB5b3UgdGhlIGZvbGxvd2luZyBwcm9ibGVtLjxcL3A+XHJcblxyXG48cD5BIHNlcXVlbmNlIGlzIGRlZmluZWQgYnkgdGhlIGZvbGxvd2luZyByZWN1cnJlbmNlOjxcL3A+XHJcblxyXG48cD5cXCh4XzAgPSAxXFwpPFwvcD5cclxuXHJcbjxwPlxcKHhfaSA9IHhfe1xcbGZsb29yIGkgLSBcXHNxcnR7aX0gXFxyZmxvb3J9ICsgeF97XFxsZmxvb3IgXFxsbnsoaSl9IFxccmZsb29yfSArIHhfe1xcbGZsb29yIGkgXFxzaW5eezJ9eyhpKX0gXFxyZmxvb3J9XFwpPFwvcD5cclxuXHJcbjxwPkRldGVybWluZSBcXCh4X3sxMDAwMDAwfVxcKS48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPklucHV0IGNvbnNpc3RzIG9mIGEgbnVtYmVyIG9mIGxpbmVzLCBlYWNoIGNvbnRhaW5pbmcgb25lIGludGVnZXIsIGEgdmFsdWUgb2YgaSwgbm8gbGVzcyB0aGFuIHplcm8gYW5kIG5vIGdyZWF0ZXIgdGhhbiBvbmUgbWlsbGlvbi4gSW5wdXQgaXMgZm9sbG93ZWQgYnkgYSBzaW5nbGUgbGluZSBjb250YWluaW5nIHRoZSBpbnRlZ2VyIC0xLiBUaGlzIGxhc3QgbGluZSBpcyBub3QgYSB2YWx1ZSBvZiBpIGFuZCBzaG91bGQgbm90IGJlIHByb2Nlc3NlZC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5Gb3IgZWFjaCB2YWx1ZSBvZiBpIGluIHRoZSBpbnB1dCAoYnV0IG5vdCB0aGUgZmluYWwgLTEpLCBvdXRwdXQgdGhlIGNvcnJlc3BvbmRpbmcgdmFsdWUgb2YgeGkgbW9kdWxvIDEwMDAwMDAuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

Contest > Waterloo's local Programming Contests > 3 October, 2009 E번

  • 문제를 번역한 사람: baekjoon
  • 문제의 오타를 찾은 사람: corea