序列的第 k 个数(c++题解)

题目描述

BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。现在给你序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第  m项的值吗。 如果第  项的值太大，对  200907取模。

输入格式

第一行一个整数 ，表示有  组测试数据；

对于每组测试数据，输入前三项 ，然后输入 。

数据保证a，b，c都是整数。数据保证若序列为等比序列则公比为整数。

输出格式

对于每组数据输出第  项的值，对  取模。

样例

样例输入

复制2
1 2 3 5
1 2 4 5

样例输出

复制5
16

样例说明

第一组是等差序列，第二组是等比数列。

_____________________________________________________________________________

写作不易，点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! 

_____________________________________________________________________________

#include <bits/stdc++.h>
using namespace std;
long long f(long long n,long long a){if(n==1)return a;if(n==0)return 1;long long x=f(n/2,a)%200907;if(n%2==0)return x*x%200907;else return a*x*x%200907;
}
long long a,b,c,n,k,ans;
int main() { cin>>n;for(long long i=1;i<=n;i++){cin>>a>>b>>c>>k;if(b-a==c-b&&b!=a){long long idx=b-a;ans=a;ans=(ans+idx*(k-1))%200907;cout<<ans<<endl;}else{long long idx=b/a;ans=a;cout<<ans%200907*f(k-1,idx)%200907<<endl;}}
}