题目描述
BSNY 在学等差数列和等比数列,当已知前三项时,就可以知道是等差数列还是等比数列。
现在给你 整数 序列的前三项,这个序列要么是等差序列,要么是等比序列,你能求出第 k
项的值吗。
如果第 k
项的值太大,对其取模 200907
。
输入格式
第一行一个整数 T
,表示有 T
组测试数据;
对于每组测试数据,输入前三项 a,b,c
,然后输入 k
。
输出格式
对于每组数据,输出第 k
项取模 200907
的值。
数据范围
1≤T≤100
,
1≤a≤b≤c≤109
,
1≤k≤109
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 200907;
LL qmi(LL a, LL b, int p)
{
LL res = 1 % p;
while(b)
{
if(b & 1) res = res * a % p;
a = a * (LL)a % p;
b >>= 1;
}
return res;
}
int t;
int main()
{
scanf("%d", &t);
while (t -- )
{
LL a, b, c, k;
scanf("%lld%lld%lld%lld", &a, &b, &c, &k);
if (b - a == c - b)
{
printf("%lld\n", (LL)(a + (k - 1) * (b - a) + mod) % mod);
}
else
{
printf("%lld\n", ((LL)a * qmi(b / a, k - 1, mod) + mod) % mod);
}
}
return 0;
}
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla