问题A：序列的第K个数
问题A：序列的第K个数
题目链接：http://acm.ocrosoft.com/problem.php?cid=1700&pid=0
题目描述
BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。现在给你序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 k 项的值吗。 如果第 k 项的值太大，对 200907 取模。
输入
第一行一个整数 T，表示有 T 组测试数据；
对于每组测试数据，输入前三项 a,b,c，然后输入 k。
对于全部数据，1<=T<=100,1<=a<=b<=c<=109,1<=k<=109
输出
对于每组数据输出第 k 项的值，对 200907 取模。
样例输入
2
1 2 3 5
1 2 4 5 样例输出
5
16 思路：对数列的情况分类讨论，之后快速幂解决
代码：
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mod 200907
int quickpow(int a,int b,int n)//快速幂
{
if (b == 1)return a;
else
{
if (b % 2 == 0)
{
ll t = quickpow(a, b / 2, n);
return t * t%n;
}
else
{
ll t = quickpow(a, b / 2, n);
t = t * t%n;
t = t * a%n;
return t;
}
}
}
int main()
{
int t;
cin >> t;
while (t--)
{
ll a, b, c, k;
cin >> a >> b >> c >> k;
if (a == b && b == c)cout << a%mod << endl;//判断是否为常数列
else if (b - a == c - b)//判断是否为等差数列
{
ll cha = b - a;
cout << (cha%mod * (k - 1)%mod)%mod + a << endl;
}
else//否则就为等比数列
{
ll q = b / a;
cout << quickpow(q, k - 1, mod)*a%mod << endl;
}
}
}
