问题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;



         }

    }

}