499
codeforces-DIV2-B- Jzzhu and Sequences
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;
}
最後更新：2017-04-03 05:39:29