题目描述

BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。

现在给你 整数 序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 k 项的值吗。

如果第 k 项的值太大，对其取模 200907。

样例

5
17 425 833 91
33 3003 5973 2
99 3960 7821 69
40 920 21160 62
20 920 42320 87

当时就是这个样例卡了我很久，直道我发现了power(b/a,k-1,200907)是要*a的

时间复杂度

参考文献

C++ 代码

#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
#define int long long
int power(int s,int t,int mod)                                  //快速幂，s是底数，t是指数
{
    int res=1;
    while(t)                                                    //t==0时退出while循环
    {
        if(t&1) res=(res*s)%mod;                                //t为奇数
        s=(s*s)%mod;                                            //s自乘
        t>>=1;                                                  //t右移一位，等于t/=2
    }
    return res;
}
signed main()
{
    int t,a,b,c,k;
    cin>>t;
    while(t--)
    {
        cin>>a>>b>>c>>k;    
        if(a+c==b+b) cout<<(a+(k-1)*(b-a))%200907<<endl;        //等差数列末项公式：（首项+（项数-1）*公差）
        else cout<<(power(b/a,k-1,200907)*a)%200907<<endl;      //快速幂，底数是公比，指数是k-1，记得要*a
    }
}

附赠等差数末项公式推导