信息学奥赛一本通 1615：【例 1】序列的第 k 个数

【题目链接】

ybt 1615：【例 1】序列的第 k 个数
本题的a 、 b 、 c a、b、ca、b、c，等差数列公差、等比数列的公比都为整数。

【题目考点】

1. 快速幂

相关知识见：洛谷 P1226 【模板】快速幂

2. 等差数列

相邻两项的差相等的数列为等差数列。
设第i ii项为a i a_iai​，公差为d dd
等差数列的递推公式：a i = a i − 1 + d a_i = a_{i-1}+dai​=ai−1​+d
等差数列的通项公式：a i = a 1 + ( i − 1 ) d a_i = a_1+(i-1)dai​=a1​+(i−1)d

3. 等比数列

相邻两项的比值相等的数列为等比数列。
设第i ii项为a i a_iai​，公比为q qq
等比数列的递推公式：a i = a i − 1 q a_i = a_{i-1}qai​=ai−1​q
等比数列的通项公式：a i = a 1 q i − 1 a_i = a_1q^{i-1}ai​=a1​qi−1

【解题思路】

设M = 200907 M=200907M=200907
每组数据，输入了数列的前三项
先判断第二项减第一项的值，与第三项减第二项的值是否相等，即是否有b − a = c − b b-a=c-bb−a=c−b
如果满足该情况，则该数列相邻两项的差相等，是等差数列。否则就是等比数列。

• 如果该数列是等差数列，则公差为b − a b-ab−a，使用通项公式求等差数列第k kk项，再对M MM取模：a k m o d M = ( a 1 + ( k − 1 ) d ) m o d M = ( a + ( k − 1 ) ( b − a ) ) m o d M a_k\bmod M=(a_1+(k-1)d)\bmod M=(a+(k-1)(b-a))\bmod Mak​modM=(a1​+(k−1)d)modM=(a+(k−1)(b−a))modM
• 如果该数列是等比数列，则公比为b a \frac{b}{a}ab​，使用通项公式求等比数列第k kk项，再对M MM取模：a k m o d M = a 1 q k − 1 m o d M = a ( b a ) k − 1 m o d M = ( a m o d M ) ( ( b a ) k − 1 m o d M ) m o d M a_k\bmod M=a_1q^{k-1}\bmod M=a(\frac{b}{a})^{k-1}\bmod M=(a\bmod M)((\frac{b}{a})^{k-1}\bmod M)\bmod Mak​modM=a1​qk−1modM=a(ab​)k−1modM=(amodM)((ab​)k−1modM)modM

求( b a ) k − 1 m o d M (\frac{b}{a})^{k-1}\bmod M(ab​)k−1modM需要用到快速幂取模算法。

本题无法使用递推公式求等差或等比数列第k kk项，因为k kk最大会达到1 0 9 10^9109，而递推求等差或等比数列第k kk项的时间复杂度是O ( n ) O(n)O(n)的，写代码运行会超时）

【题解代码】

解法1：快速幂

#include<bits/stdc++.h>usingnamespacestd;typedeflonglongLL;constintM=200907;LLfastPow(LL a,LL b,LL m){LL r=1;while(b>0){if(b%2==1)r=r*a%m;a=a*a%m;b/=2;}returnr;}intmain(){LL t,a,b,c,k;cin>>t;while(t--){cin>>a>>b>>c>>k;if(c-b==b-a)cout<<(a+(k-1)*(b-a))%M<<endl;else//c/b == b/acout<<a*fastPow(b/a,k-1,M)%M<<endl;}return0;}