AcWing 1289. 序列的第k个数

题目传送门

一、疑问：能不能一个数列，即是等差数列又是等比数列?

结论：一个数列如果是即是等差又是等比，那么它必然是一个全等数列
证明：
设三个连续数字\(a\ b \ c\),
等差数列，所以\(a+c=2b\) ①
等比数列，所以\(\frac{b}{a}=\frac{c}{b}\),所以\(b^2=ac\) ②

将\(a=2b-c\)代入②
\(b^2=(2b-c)*c\)
\(b^2=2bc-c^2\)
\(b^2-2bc+c^2=0\)
\((b-c)^2=0\)
∴\(b=c\)

由此可知，题目中给了数列的前三项，存在可能即是等差又是等比的情况，但，此时就是一个全等数列，按哪个规则进行计算都是一样的结果，题目不缺少条件。

二、题意分析

• 等差数列
  公差\(d=b-a\)
  第\(k\)项，应该是\(a+(k-1)d\)，这个很好求，直接求然后注意取模就行了。

• 等比数列
  公比\(p=\frac{b}{a}\)
  第\(k\)项,应该是\(a*p^{k-1}=a*(\frac{b}{a})^{k-1}\)

三、实现代码

#include 
using namespace std;

//快速幂
typedef long long LL;
const int mod = 200907;
int qmi(int a, int k) {
    int res = 1;
    while (k) {
        if (k & 1) res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}

int main() {
    int n;
    scanf("%d", &n);
    while (n--) {
        int a, b, c, k;
        scanf("%d%d%d%d", &a, &b, &c, &k);
        if (a + c == b * 2) //等差
            printf("%lld\n", (a + (b - a) * (LL)(k - 1)) % mod);
        else //等比
            printf("%lld\n", (LL)a * qmi(b / a, k - 1) % mod);
    }

    return 0;
}