51nod--1126 求递推序列的第N项

题目描述

基准时间限制：1 秒 空间限制：131072 KB 分值: 10 难度：2级算法题 收藏 关注
有一个序列是这样定义的：f(1) = 1, f(2) = 1, f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
给出A，B和N，求f(n)的值。
Input
输入3个数：A,B,N。数字之间用空格分割。(-10000 <= A, B <= 10000, 1 <= N <= 10^9)
Output
输出f(n)的值。
Input示例
3 -1 5
Output示例
6

标题

/* 解题思路：lz历经了三个变化； 第一。一看题，这么简单，于是就写了个数组版本的递推。结果爆栈了。 第二：于是马上想到了用3个变量来递推， 结果超时了 第三：于是苦思冥想，难道还有logn的解法吗 于是就去百度了，一看，原来是有规律可循的。 于是就ac了。 */

标题

import java.util.Scanner;
public class Main{

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int A = sc.nextInt();
        int B = sc.nextInt();
        int N = sc.nextInt();
        //init
        int[] f = new int[50];
        if(N==1 || N==2){
            System.out.println("1");
            return;
        }
        f[1] = 1;
        f[2] = 1;
        int i = 0;
        //process
        for(i=3; i<50; ++i){
            f[i] = ((A*f[i-1] + B*f[i-2]) % 7+ 7) % 7;
// System.out.println(f[i]+" ");
            if(f[i]==1 && f[i-1]==1)
                break;
        }
// if(N % (i-2) ==0)
           f[0] = f[i-2];
        System.out.println(f[N%(i-2)]);
    }
}