Codeforces 450B - 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).
Input:
The first line contains two integers x and y (|x|, |y| ≤ 109). The second line contains a single integer n (1 ≤ n ≤ 2·109).
Output:
Output a single integer representing fn modulo 1000000007 (109 + 7).
範例:
input:
1 | 2 3 |
output:
1 | 1 |
input:
1 | 0 -1 |
output:
1 | 1000000006 |
Note:
In the first sample, f2 = f1 + f3, 3 = 2 + f3, f3 = 1.
In the second sample, f2 = - 1; - 1 modulo (109 + 7) equals (109 + 6).
題意:
輸入X跟Y作為一個數列的前兩項，並給你數列的規則，問你第N項對100000007取餘數後的值是多少？
思路:
將規則用X跟Y繼續列舉，發現每6項數值會有一個循環，因此先將前6項計算好，再計算第N項是6項中的第幾項後就可以取餘數了，要注意的是餘數是負數的時候要加回正數。