序列的### 第 k 个数

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 875 字

给定序列前三项，判断等差或等比，求第k项对2

一本通
例

正文

/*
原题：序列的第 k 个数
题意：给定序列前三项，判断等差或等比，求第 k 项对 200907 取模。
思路：若 b-a==c-b 则为等差，第 k 项为 a+(k-1)*d；否则等比，公比 q=b/a，第 k 项为 a*q^(k-1) mod 200907，用快速幂。
复杂度：O(T log k) 时间 / O(1) 空间
易错点：等比时 q 用 long long 存储；乘法后及时取模防溢出；等差等比判定准确。
*/
#include <bits/stdc++.h>
using namespace std;
const int MOD=200907;
long long qpow(long long a,long long b){
    long long res=1%MOD;
    a%=MOD;
    while(b){
        if(b&1){ res=res*a%MOD; }
        a=a*a%MOD;
        b>>=1;
    }
    return res;
}
int main(){
    int T;
    cin>>T;
    while(T--){
        long long a,b,c,k;
        cin>>a>>b>>c>>k;
        long long ans;
        if(b-a==c-b){
            // 等差数列
            long long d=b-a;
            ans=(a%MOD+(k-1)%MOD*(d%MOD)%MOD)%MOD;
        }else{
            // 等比数列
            long long q=b/a;
            ans=a%MOD*qpow(q,k-1)%MOD;
        }
        cout<<ans<<'\n';
    }
    return 0;
}

序列的### 第 k 个数

正文

一本通·提高篇的其它内容