AcWing 1289. 序列的第k个数

一.题目链接

二.思路

一共T组测试数据，给出一个数列的前三项a,b,c。判断是等差数列还是等比数列，求该数列的第k项。

• 性质：一个数列既是等差数列又是等比数列 当且仅当 a = b = c。
  第一步：判断是等差还是等比
  情况1：公差：$d=b-a$ 答案：$ans=a+(k-1)d$
  情况2：公比：$q=\frac{b}{a}$ 答案：$ans=a\ast p^{k-1}$
  第二步：当为公比的时候，直接用快速幂求解即可。

三.代码

#include 
#include 
#include 

using namespace std;
const int mod = 200907;
typedef long long ll;
//快速幂
int qmi(int a, int b)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (ll) res * a % mod;
        a = (ll)a * a % mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    int T;
    cin >> T;
    while(T --)
    {
        int a, b, c, k;
        scanf("%d%d%d%d", &a, &b, &c, &k);
        //判断是否是等差数列
        if(a + c == 2 * b) cout << (a + (ll)(k - 1) * (b - a)) % mod << endl;
        else
        {
            cout << (ll)a * qmi((b / a), k - 1) % mod << endl;
        }
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

四.总结

给出数列前三项a,b,c。

1. 若为等差数列 当且仅当 $a\ast c=2\ast b$
2. 若为等比数列 当且仅当 $a\ast c=b^2$
3. 等差数列前n项和：
   $S_n=\frac{(a_1+a_n)n}{2}$
   $S_n=n{a}_1+\frac{n(n-1)}{2}d$
4. 等比数列前n项和：
   $S_n=\frac{a_1(1-q^n)}{1-q}(q不等于1)$