序列的第k个数

快速幂 T2 https://www.luogu.com.cn/problem/U267088

题目描述

你在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。现在给你序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 k 项的值吗。 如果第 k 项的值太大，对 200907 取模。

输入格式

第一行一个整数 T，表示有 T 组测试数据；

对于每组测试数据，输入前三项 a,b,c，然后输入 k。

输出格式

对于每组数据输出第 k 项的值，对 200907 取模。

样例 #1

样例输入 #1

2
1 2 3 5
1 2 4 5

样例输出 #1

5
16

提示

解释：第一组是等差序列，第二组是等比数列。

【数据范围与提示】 对于全部数据，1⇐ T⇐100,1⇐ a⇐ b⇐ c⇐ 10^9,1⇐ k⇐ 10

思路

若是等差数列， 求出 d 后， 第 k 项就是 $a+d\times k\mathrm{mod}MOD$ 。若是等比数列， 求出 p 后， 第 k 项就是 $a\times p^k\mathrm{mod}MOD$ 。

已知前三项$a,b,c$， 定义 $d_1=b-a,d_2=c-b$, 若 $d_1=d_2$ 则说明有可能是等差数列,在 $d_1=d_2=0$ 时既是等比也是等差， 若 $d_2\mathrm{mod}{d}_1=0$ 且 $d_1\ne d_2$ 则说明是等比数列。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MOD = 200907;
 
int qmi(LL a, LL b, int p)
{
    int res = 1;
    while(b)
    {
        if(b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}
 
void solve() {
    LL a, b, c, k;
    cin >> a >> b >> c >> k;
    LL d1 = b - a, d2 = c - b;
    if(d1 == 0 && d2 == 0) cout << a << endl;
    else if(d1 == d2) cout << (a + (k-1)*d1 % MOD) % MOD << endl;
    else cout << (a * qmi(d2 / d1, k-1, MOD)) % MOD << endl;
}
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    //cout << (LL)1000000000 % MOD << endl;
    int T;
    cin >> T;
    while(T--)
        solve();
    return 0;
}