对快速幂的考察,侧重于快速幂取模以及大数的取模运算。
输入由两种情况组成:几何序列和算术序列,分别对应等比数列和等差数列。
对于等差数列的判断相对非常简单,只需要判断前三项是否满足等差条件,如满足
条件则求出公差,利用等差数列公式求解就可以了,不要忘记取模。
对于等比数列,求一个数列的第K项,也就是求这个数列从第二项开始数第K-1项,由等比数列公式
an=a1×q^(n-1),可得,先求出公比的k-1次方,然后再乘第一个数就可以了。也不要忘记取模运算。
1 #include <iostream> 2 typedef long long LL; 3 using namespace std; 4 LL a, b, c, k; 5 LL ans(){ 6 return (a % 200907 + ((k - 1) % 200907) * ((b - a) % 200907)) % 200907; 7 } 8 LL res(){ 9 LL res = 1; 10 LL base = b / a; 11 LL temp = k - 1; 12 while(temp){ 13 if(temp & 1) 14 res = (res * base) % 200907; 15 base = (base * base) % 200907; 16 temp >>= 1; 17 } 18 return res; 19 } 20 int main(){ 21 int n; 22 cin >> n; 23 while(n--){ 24 cin >> a >> b >> c >> k; 25 if(a == b) 26 cout << a % 200907 << endl; 27 else if(b - a == c - b){ 28 cout << ans() << endl; 29 }else 30 cout << (res() * (a % 200907)) % 200907 << endl; 31 } 32 33 return 0; 34 }