시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 96 40 28 36.842%

문제

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

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

\(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로 나눈 나머지를 출력한다.

예제 입력

0
-1

예제 출력

1

힌트

출처

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

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