学步园

 Jzzhu and Sequences

Jzzhu has invented a kind of sequences, they meet the following property:

You are given x and y, please calculate fn modulo 1000000007 (109 + 7).

InputThe first line contains two integers x and y (|x|, |y| ≤ 109). The second line contains a single integer n (1 ≤ n ≤ 2·109).

OutputOutput a single integer representing fn modulo 1000000007 (109 + 7).

Sample test(s)input

2 3
3

output

1

input

0 -1
2

output

1000000006

NoteIn the first sample, f2 = f1 + f3, 3 = 2 + f3, f3 = 1.

In the second sample, f2 =  - 1;  - 1 modulo (109 + 7) equals (109 + 6).

斐波那契数列+负数取余+找规律

AC代码:

#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
int main()
{
    int i,j,n,m,f1,f2,f3;
    scanf("%d %d",&f1,&f2);
    scanf("%d",&n);
    if(n<3)
    {
       if(n==1)
       {
           if(f1<0)
           printf("%d\n",f1+1000000007);
           else
           printf("%d\n",f1%1000000007);
       }
       else
       {
           if(f2<0)
           printf("%d\n",f2+1000000007);
           else
           printf("%d\n",f2%1000000007);
       }
    }
    else
    {
        n=(n-3)%6+3;
        for(j=3;j<=n;j++)
        {
           f3=(f2-f1);
           if(f2<0)
           {
              f2=f2+1000000007; 
           }
           else
           f2=f2%1000000007;
           f1=f2;
           if(f3<0)
           {
              f3=f3+1000000007;    
           }
           else
           f3=f3%1000000007;
           f2=f3;
        }
        printf("%d\n",f3%1000000007);  
    }
    return 0;
}