题目描述

A number sequence is defined as follows:

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

Given A, B, and n, you are to calculate the value of f(n).

输入

The input consists of multiple test cases. Each test case contains 3 integers A, B and n on a single line (1 <= A, B <= 1000, 1 <= n <= 100,000,000). Three zeros signal the end of input and this test case is not to be processed.

输出

For each test case, print the value of f(n) on a single line.

示例输入

1 1 31 2 100 0 0

示例输出

25

提示

知识扩展：本类算法在数字医疗、移动证券、手机彩票、益智类解谜类游戏软件中会经常采用。

来源

1 #include
      
        2 using namespace std ; 3 int main() 4 { 5     int a, b, n, f[60] ; 6     int flag, i, j, start, end ; 7     while(cin>>a>>b>>n) 8     { 9         flag = 0 ;10         if(a==0&&b==0&&n==0) break ;11         f[1] = f[2] = 1 ;12         for(i=3; i<=n&&!flag; i++)13         {14             f[i] = (a*f[i-1]+b*f[i-2])%7 ;//所给公式15             for(j=2; j < i; j++)//查找循环结点16             {17                 if(f[i]==f[j]&&f[i-1]==f[j-1])18                 {19                     start = j ;//初始位置20                     end = i ;//终点位置21                     flag = 1 ;//找到的标志22                     break ;//一旦找到循环结点，退出，节省时间23                 }24             }25         }26         if(flag) cout<
       
        <
       
      

f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.

f(1)可取 0 1 2 3 4 5 6 ；

f(2)可取 0 1 2 3 4 5 6;

A B 固定所以两两组合共有 49 中情况

所以这是一个循环的方程；