杭电ACM 1005：Number Sequence

Problem Description

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).

Input

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.
Output

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

Sample Input

1 1 3

1 2 10

0 0 0

Sample Output

2

5

C语言代码，转自：http://neuxxm.is-programmer.com/posts/26894.html

#include <stdio.h>
#include <string.h>
int main(){
    int b[7][7];
    int a[100];
    int n;
    int x, y, m, st, len;
    while (scanf("%d %d %d", &x, &y, &m) == 3){
        if (x==0 && y==0 && m==0){
            break;
        }
        a[1] = 1;
        a[2] = 1;
        memset(b, 0, sizeof(b));
        b[1][1] = 1;
        n = 3;
        for (;;){
            a[n] = (a[n-1]*x+a[n-2]*y)%7;
            if (b[a[n-1]][a[n]] != 0){
                break;
            }
            b[a[n-1]][a[n]] = n-1;
            ++n;
        }
        st = b[a[n-1]][a[n]];
        len = n-1-st;
        if (m < st){
            printf("%d\n", a[m]);
        }
        else{
            printf("%d\n", a[st+(m-st)%len]);
        }
    }
    return 0;
}

C++代码，代码来源：http://blog.163.com/jackie_howe/blog/static/1994913472012319111457714/

#include<iostream>
using namespace std;
int main()
{
 int a,b,n;
 cin>>a>>b>>n;
 while(a!=0 || b!=0 || n!=0)
 {
  int str[2]={1,1};
  for(int i=0;i<(n%49-1)/2;i++)
  {
   str[0]=(a*str[1]+b*str[0])%7;
   str[1]=(a*str[0]+b*str[1])%7;
  }
  if(n%2)
  {
   cout<<str[0]<<endl;
  }
  else
  {
   cout<<str[1]<<endl;
  }
  cin>>a>>b>>n;
 }
 return 0;
}