序列的第k个数
题目 序列的第k个数
BSNY 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。
现在给你 整数 序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 k 项的值吗。
如果第 k 项的值太大，对其取模 200907。
输入格式 第一行一个整数 T，表示有 T 组测试数据；
对于每组测试数据，输入前三项 a,b,c，然后输入 k。
输出格式 对于每组数据，输出第 k 项取模 200907 的值。
数据范围 1≤T≤100, 1≤a≤b≤c≤10^9, 1≤k≤10^9
输入样例： 2 1 2 3 5 1 2 4 5
输出样例： 5 16
思路分析
暴力模拟 因为题目说了 数据要么是等差要么是等比 不会出现即是又是 都不是的情况
所以能首先根据前三项确定是等差还是等比 再根据等差数列 等比数列 第n项的公式求得解
#include<bits/stdc++.h>
using namespace std;
int main()
{
int T;cin>>T;
while(T--){
int a1,a2,a3,n;
cin>>a1>>a2>>a3>>n;
if(a3-a2==a2-a1){
//cout<<"等差"<<endl;//an=a1+(n-1)d
int d=a3-a2;
cout<<a1+(n-1)*d<<endl;
}
else if(a3/a2==a2/a1){
// cout<<"等比"<<endl;//a1*q^(n-1)
int q=a3/a2;
cout<<a1*(pow(q,n-1))<<endl;
}
}
return 0;
}
提高课的题 没买进不去 测试不了能过几个数据
优化：
一个数列，如果既是等差数列，有是等比数列，那么这个数列必然是恒等序列
证明：（利用等差、等比中项）
等差、等比对应两类情况
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 200907;
int t,a,b,c,k;
int qmi(int a,int b)
{
int res = 1;
while(b){
if(b&1)
res = res * a % mod;
b>>=1;
a = a * a % mod;
}
return res;
}
signed main()
{
cin>>t;
while(t--){
cin>>a>>b>>c>>k;
if(a+c==2*b)
cout << (a + (b - a) * (k - 1) % mod) % mod << endl;
else if(a*c==b*b)
cout<< a * qmi(b / a, k - 1) % mod<<endl;
}
return 0;
}
乐 这就是数论呢 考试的时候回忆得起两个公式就谢天谢地了
代码实现
💬 评论