爱站程序员基地HDU 2817
Problem Description
Xinlv wrote some sequences on the paper a long time ago, they might be arithmetic or geometric sequences. The numbers are not very clear now, and only the first three numbers of each sequence are recognizable. Xinlv wants to know some numbers in these sequences, and he needs your help.
Input
The first line contains an integer N, indicting that there are N sequences. Each of the following N lines contain four integers. The first three indicating the first three numbers of the sequence, and the last one is K, indicating that we want to know the K-th numbers of the sequence.
You can assume 0 < K <= 10^9, and the other three numbers are in the range [0, 2^63). All the numbers of the sequences are integers. And the sequences are non-decreasing.
Output
Output one line for each test case, that is, the K-th number module (%) 200907
Sample Input
2
1 2 3 5
1 2 4 5
Sample Output
5
16
题目大致意思是给你4个数字a,b,c,k,前面3个数字a,b,c能够构成等差或者等比数列（需要你自己去判断是否构成等差或者等比数列），让你去取这个数列中第k个数。
思路
判断的话就用a+c=2*b来判断，如果满足的话就是等差数列，如果不满足的话就是等比数列，这应该能够容易想到。
求数列中第k个的话，等差数列是容易的，就是用等差数列的通项公式a1+(n-1)*d(a1是首项，n是第几个，d是公差)来求。等比就比较难求了，虽然也是通过通向公式来求，可是只是简简单单的相乘，10^9，会TAT的。所以这里就要用到快速幂了。
这里简单的介绍一下快速幂。快速幂就是高效地求出a^n，
快速幂的实现：先算出a的2次方，然后继续算平方a的二次的平方。
代码实现：
LL fas(LL q,LL n){LL r = 1;while(n){if(n&1)r = r * q;n /= 2;q = q * q;}return r;}
这道题的求等比数列的第k个就是用这个来求。
以下就是这题的ac代码：
#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>using namespace std;typedef long long LL;const int mode = 200907;LL fas(LL q,LL n){LL r = 1;while(n){if(n&1)r = (r%mode * (q%mode)) % mode;n /= 2;q = (q%mode * (q%mode)) % mode;}return r;}int main(){LL t;cin>>t;LL a, b, c, k;LL y;while(t--){cin >> a >> b >> c >> k;if(a+c==2*b){LL e = (c - b) ;y = ((e) * ((k - 1) ) % mode + a) % mode;}else {LL q=b/a;y = (a * fas(q, k - 1) % mode);}cout << y << endl;}}
道阻且长，
自己选的路 跪着也要走完。
