「一本通 6.1 例 1」序列的第 k 个数

题目描述

BSNY 已知一个数列的前三项 $a,b,c$ ，该数列要么为等差数列、要么为等比数列。给定 $k$ ，求第 $k$ 项对 $200907$ 取模的值。多组数据。

输入：先读 $T$ ，随后 $T$ 行每行 $a\ b\ c\ k$ 。输出：每组一行答案。

数据范围： $1\le T\le100,\ 1\le a\le b\le c\le10^9,\ 1\le k\le10^9$ 。

思路

若 $2b=a+c$ 则为等差数列，公差 $d=b-a$ ，答案为 $a+(k-1)d$ 。否则为等比数列，公比 $r=b/a$ ，答案为 $a\cdot r^{k-1}\bmod 200907$ ，其中幂用快速幂在模意义下计算。

参考代码

Python 版：

python

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
37#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-09-30 22:19
# update_at: 2026-09-30 22:19

import sys

MOD = 200907  # 题目指定的模数


def nth_term(a: int, b: int, c: int, k: int) -> int:
    """前三项为 a,b,c 的等差或等比序列，求第 k 项对 MOD 的值。"""
    is_arith = 2 * b == a + c  # 前三项等差 ⇔ 中项的两倍等于首尾和；否则必为等比
    if is_arith:
        # 等差通项 a + (k-1)d，d = b-a ≥ 0；k 可达 1e9，先取模再输出
        return (a + (k - 1) * (b - a)) % MOD
    # 等比通项 a·r^(k-1)，公比 r = b/a 为整数（数据保证 a 整除 b）；
    # 三参数 pow 是二进制快速幂，O(log k) 次乘法边乘边取模
    return a % MOD * pow(b // a, k - 1, MOD) % MOD


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)

    out: list[str] = []
    for _ in range(T):
        a, b, c, k = next(data), next(data), next(data), next(data)
        out.append(str(nth_term(a, b, c, k)))

    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

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
37
38
39
40
41
42
43
44
45
46
47/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 01:04
 * update_at: 2026-10-06 01:04
 */

#include <cstdio>

using namespace std;

typedef long long ll;

const ll MOD = 200907;

ll T, a, b, c, k;

// 快速幂：返回 base^exp mod MOD
ll qpow(ll base, ll exp) {
    ll res = 1 % MOD;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = res * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return res;
}

int main() {
    scanf("%lld", &T);
    while (T--) {
        scanf("%lld %lld %lld %lld", &a, &b, &c, &k);
        ll ans;
        if (2 * b == a + c) { // 等差数列
            ll d = b - a;
            // 通项 a+(k-1)d，模意义下运算
            ans = ((a % MOD) + (((k - 1) % MOD) * (d % MOD)) % MOD) % MOD;
        } else { // 等比数列，题面保证 r 为整数
            ll r = b / a;
            ans = ((a % MOD) * qpow(r, k - 1)) % MOD;
        }
        printf("%lld\n", ans);
    }
    return 0;
}

「一本通 6.1 例 1」序列的第 k 个数

目录

题目描述

思路

参考代码