题目1442：A sequence of numbers 时间限制：1 秒内存限制：128 兆特殊判题：否提交：4184解决：1066 题目描述： Xinlv wrote some sequences on the paper a long time ago, they might be arithmetic or geometric sequences. The numbers are not very clear now, and only the first three numbers of each sequence are recognizable. Xinlv wants to know some numbers in these sequences, and he needs your help. 输入： The first line contains an integer N, indicting that there are N sequences. Each of the following N lines contain four integers. The first three indicating the first three numbers of the sequence, and the last one is K, indicating that we want to know the K-th numbers of the sequence. You can assume 0 < K <= 10^9, and the other three numbers are in the range [0, 2^63). All the numbers of the sequences are integers. And the sequences are non-decreasing. 输出： Output one line for each test case, that is, the K-th number module (%) 200907. 样例输入： 2 1 2 3 5 1 2 4 5 样例输出： 5 16 问题分析： 先根据等比或等差数列判断属于那种数列，然后利用对于数列的通项公式进行求解。 对于等差数列，整除求解即可； 对于等比数列，在通项an=a1*q^(n-1)时，q^(n-1)用二分去幂法求解。 代码：
#include <iostream> #define M 200907 using namespace std; /* run this program using the console pauser or add your own getch, system("pause") or input loop */ bool isArithmetic(long long *num){ bool ans=false; //若满足等差中项公式 则为等差 ；若满足等比中项公式，则为等比 //cout<<2*num[1]<<" "<<num[0]*num[2]<<endl; if(2*num[1] == num[0]+num[2]) { ans = true; } return ans; } long long power(long long num,long long a,long long b){ long long ans=num; //二分法快速求幂 while(b != 0){ if(b%2 == 1){ ans=(ans*a)%M; //按题目要求对结果取模 } a=(a*a)%M; //累乘 按题目要求对结果取模 b/=2; //求下一位二进制数 } return ans; } int main(int argc, char *argv[]) { int N; while(cin>>N){ while(N--){ //1.输入数据 long long num[3]; for(int i=0;i<3;i++){ cin>>num[i]; } long long k; cin>>k; long long ans; //2.判断是arithmetic squences or geometric sequences if(isArithmetic(num) == true){ //是算术序列 //cout<<"Arithmetic"<<endl; ans=num[0]%M+((num[1]-num[0])%M)*((k-1)%M)%M; //等差数列第n项公式 } else //是几何序列 { //cout<<"NO"<<endl; long long p=num[2]/num[1]; //ans=(num[0]%M)*(power(num[0],p,k-1)%M); //等比数列第n项公式 ans=power(num[0],p,k-1)%M; } cout<<ans<<endl; } } return 0; }代码分析： //ans=(num[0]%M)*(power(num[0],p,k-1)%M); //等比数列第n项公式 ans=power(num[0],p,k-1)%M; num[0]%M)放在外面总是不能AC，不知道为什么。
