시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 381 155 120 43.165%

문제

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

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

\(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+XHJcblxyXG48cD5cdWIyZTRcdWM3NGNcdWFjZmMgXHVhYzE5XHVjNzc0IFx1YzdhY1x1YWRjMFx1YzgwMVx1YzczY1x1Yjg1YyBcdWM4MTVcdWM3NThcdWI0MWMgXHVjMjE4XHVjNWY0XHVjNzc0IFx1Yzc4OFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XFwoeF8wID0gMVxcKTxcL3A+XHJcblxyXG48cD5cXCh4X2kgPSB4X3tcXGxmbG9vciBpIC0gXFxzcXJ0e2l9IFxccmZsb29yfSArIHhfe1xcbGZsb29yIFxcbG57KGkpfSBcXHJmbG9vcn0gKyB4X3tcXGxmbG9vciBpIFxcc2luXnsyfXsoaSl9IFxccmZsb29yfVxcKTxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI1NGMsIFxcKHhfezEwMDAwMDB9XFwpXHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YzJkY1x1YzYyNC48XC9wPlxyXG5cclxuPHA+XFwoaVxcKVx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM4NGNcdWM3NDQgXHViNTRjLCBcXCh4X2lcXClcdWI5N2MgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWM3ODVcdWI4MjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMxY1x1Yzc1OCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHViODVjIFx1Yzc3NFx1YjhlOFx1YzViNFx1YzgzOCBcdWM3ODhcdWM3M2NcdWJhNzAsIFx1ZDU1YyBcdWM5MDRcdWM1ZDAgXHVkNTU4XHViMDk4XHVjNTI5IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1YzkwNFx1YzVkMFx1YjI5NCZuYnNwO1xcKGlcXClcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViYTcwLCBcdWM3NzQgXHVjMjE4XHViMjk0IDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVjOWMwIFx1YzU0YVx1YWNlMCwgXHViYzMxXHViOWNjXHViY2Y0XHViMmU0IFx1ZDA2Y1x1YzljMCBcdWM1NGFcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1Yzc4NVx1YjgyNVx1Yzc1OCBcdWI5YzhcdWM5YzBcdWI5YzkgXHVjOTA0XHVjNWQwXHViMjk0IC0xXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljMFx1YmE3MCwgXHVjNzc0IFx1YzIxOFx1YjI5NCBcdWM3ODVcdWI4MjVcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5XHVjNzQ0IFx1YjA5OFx1ZDBjMFx1YjBiNFx1YjI5NCBcdWMyMThcdWM3NzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjNzg1XHViODI1XHVjNzNjXHViODVjIFx1YzhmY1x1YzViNFx1YzljNCBcXChpXFwpXHViOWM4XHViMmU0IFxcKHhfaVxcKVx1Yjk3YyAxMDAwMDAwXHViODVjIFx1YjA5OFx1YjIwOCBcdWIwOThcdWJhMzhcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjQxNzIiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJzcXJ0IGxvZyBzaW4iLCJkZXNjcmlwdGlvbiI6IjxwPkFuIGV2aWwgcHJvZmVzc29yIGhhcyBqdXN0IGFzc2lnbmVkIHlvdSB0aGUgZm9sbG93aW5nIHByb2JsZW0uPFwvcD5cclxuXHJcbjxwPkEgc2VxdWVuY2UgaXMgZGVmaW5lZCBieSB0aGUgZm9sbG93aW5nIHJlY3VycmVuY2U6PFwvcD5cclxuXHJcbjxwPlxcKHhfMCA9IDFcXCk8XC9wPlxyXG5cclxuPHA+XFwoeF9pID0geF97XFxsZmxvb3IgaSAtIFxcc3FydHtpfSBcXHJmbG9vcn0gKyB4X3tcXGxmbG9vciBcXGxueyhpKX0gXFxyZmxvb3J9ICsgeF97XFxsZmxvb3IgaSBcXHNpbl57Mn17KGkpfSBcXHJmbG9vcn1cXCk8XC9wPlxyXG5cclxuPHA+RGV0ZXJtaW5lIFxcKHhfezEwMDAwMDB9XFwpLjxcL3A+XHJcbiIsImlucHV0IjoiPHA+SW5wdXQgY29uc2lzdHMgb2YgYSBudW1iZXIgb2YgbGluZXMsIGVhY2ggY29udGFpbmluZyBvbmUgaW50ZWdlciwgYSB2YWx1ZSBvZiBpLCBubyBsZXNzIHRoYW4gemVybyBhbmQgbm8gZ3JlYXRlciB0aGFuIG9uZSBtaWxsaW9uLiBJbnB1dCBpcyBmb2xsb3dlZCBieSBhIHNpbmdsZSBsaW5lIGNvbnRhaW5pbmcgdGhlIGludGVnZXIgLTEuIFRoaXMgbGFzdCBsaW5lIGlzIG5vdCBhIHZhbHVlIG9mIGkgYW5kIHNob3VsZCBub3QgYmUgcHJvY2Vzc2VkLjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPkZvciBlYWNoIHZhbHVlIG9mIGkgaW4gdGhlIGlucHV0IChidXQgbm90IHRoZSBmaW5hbCAtMSksIG91dHB1dCB0aGUgY29ycmVzcG9uZGluZyB2YWx1ZSBvZiB4aSBtb2R1bG8gMTAwMDAwMC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=

출처

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

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