1289. 序列的第k个数
BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。
现在给你?整数?序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第?kk?项的值吗。
如果第?kk?项的值太大，对其取模?200907200907。
输入格式
第一行一个整数?TT，表示有?TT?组测试数据；
对于每组测试数据，输入前三项?a,b,ca,b,c，然后输入?kk。
输出格式
对于每组数据，输出第?kk?项取模?200907200907?的值。
数据范围
1≤T≤1001≤T≤100,
1≤a≤b≤c≤1091≤a≤b≤c≤109,
1≤k≤1091≤k≤109
输入样例：
2
1 2 3 5
1 2 4 5
输出样例：
5
16
代码：
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int N = 200907;
signed main(){
long long n;
cin>>n;
while (n -- ){
int a,b,c,d;
cin>>a>>b>>c>>d;
if(b-a==c-b){
int cnt=b-a;
d--;
while(d){
if(d&1)
a+=cnt;
a%=N;
cnt*=2;
d>>=1;
}
cout<<a<<endl;
}
else{
int cnt=1;
int cntt=(b/a);
d--;
while(d){
if(d&1){
cnt*=cntt;
cnt=(cnt+N)%N;
}
cntt*=cntt;
cntt=(cntt+N)%N;
d>>=1;
}
a*=cnt;
a=(a+N)%N;
cout<<a<<endl;
}
}
}
|