HDU2817 A sequence of numbers

对快速幂的考察,侧重于快速幂取模以及大数的取模运算。

输入由两种情况组成:几何序列和算术序列,分别对应等比数列和等差数列。

对于等差数列的判断相对非常简单,只需要判断前三项是否满足等差条件,如满足

条件则求出公差,利用等差数列公式求解就可以了,不要忘记取模。

对于等比数列,求一个数列的第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 }

 

上一篇:信息学奥赛一本通 提高篇 序列第k个数 及 快速幂


下一篇:数列求值