으아악문제 설명
숫자 순서는 다음과 같이 정의됩니다.
f(1) = 1, f(2) = 1, f(n) = (A f(n - 1) + B f(n - 2)) mod 7.
A, B, n이 주어졌을 때 f(n)의 값을 계산해야 합니다.
입력
입력은 여러 테스트 사례로 구성됩니다. 각 테스트 케이스
에는 한 줄에 3개의 정수 A, B, n이 포함되어 있습니다(1 <= A, B <= 1000, 1
<= n <= 100,000,000). 3개의 0은 입력이 끝났다는 신호이며 이
테스트 케이스는 처리되지 않습니다.출력
각 테스트 케이스에 대해 f(n) 값을 한 줄에 인쇄하세요.
샘플 입력
1 1 3
1 2 10
0 0 0
샘플 출력
2
5
온라인에는 문제 해결 보고서가 없나요? 이 질문은 패턴을 찾고 있습니다. 이 질문의 q는 기간 T를 찾고 있습니다. 왜 우리가 처음 54개만 찾는지에 대해서는 엄격한 수학적 추론이 필요합니다. 테스트한 결과 53은 괜찮지만 52 미만은 아닌 것으로 나타났습니다.
---------------여담-------------
이런 질문은 언뜻 보면 테이블을 만들거나 패턴을 찾는 것과 비슷해요.
이 질문이 틀린 질문이 아니라는 전제하에 이런 질문을 해결하는 방법에는 분명히 두 가지가 있습니다. 폭력적인 테이블 만들기 또는 패턴 찾기 전자는 이 질문이 큰 질문이라는 의미이고 후자는 이 질문이라는 의미입니다. 물은 추론의 어려움에 달려 있지만 이 질문에 관한 한 그것은 큰 물 문제입니다. 인터넷에 있는 문제 해결 보고서를 보면 어떤 사람들은 직접 배열을 엽니다. 1000 그들이 기간을 찾아 뛰어 내릴 때까지.
다음 토론은 제한됩니다
i>=1
:분명히
f(i) in { 0 .. 6}
그래서
<f(i-2), f(i-1)>
이 상태 공간은 제한되어 있으며 최대값은 49그래서
f(i)
에는 마침표가 있고 49는 마침표입니다그런 다음 전체 주기를 열거하고 주기에서
f(n)
와 같은 위치에 있는 숫자추가됨:
q는 가장 짧은 기간이 아닙니다. 사실 첫 번째 기간을 찾으면 중지할 수 있습니다.
n이 49의 배수일 때 반환되어야 합니다.
f[0]=0
버그일 수 있습니다