C++ 等差数列和等比数列求第 P 项 - 代码详解

C++ 等差数列和等比数列求第 P 项 - 代码详解

题目描述

辰辰在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。

现在给你序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 'P' 项的值吗？

如果第 'P' 项的值太大，对 200907 取模。

输入格式

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

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

输出格式

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

样例

输入数据 1 2 1 2 3 5 1 2 4 5

输出数据 1 5 16

样例解释

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

数据范围

对于全部数据，1 ≤ T ≤ 100, 1 ≤ a ≤ b ≤ c ≤ 10^9 , 1 ≤ P ≤ 10^3 。

C++ 代码实现

#include <iostream>
using namespace std;

// 求a^b对mod取模的结果
long long powMod(long long a, long long b, long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b & 1) {
            res = (res * a) % mod;
        }
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}

// 求等差数列的第P项
long long arithmeticSequence(long long a, long long b, long long c, long long P) {
    long long d = b - a;  // 公差
    long long res = (a + (P - 1) * d) % 200907;
    return res;
}

// 求等比数列的第P项
long long geometricSequence(long long a, long long b, long long c, long long P) {
    long long q = b / a;  // 公比
    long long res = (a * powMod(q, P - 1, 200907)) % 200907;
    return res;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        long long a, b, c, P;
        cin >> a >> b >> c >> P;
        if (b - a == c - b) {
            // 等差数列
            cout << arithmeticSequence(a, b, c, P) << endl;
        } else {
            // 等比数列
            cout << geometricSequence(a, b, c, P) << endl;
        }
    }
    return 0;
}

代码解析

1. powMod 函数: 用于计算 a^b 对 mod 取模的结果，采用快速幂算法，时间复杂度为 O(log b)。
2. arithmeticSequence 函数: 用于计算等差数列的第 P 项，根据等差数列的通项公式计算。
3. geometricSequence 函数: 用于计算等比数列的第 P 项，根据等比数列的通项公式计算，并利用 powMod 函数进行快速幂运算。
4. main 函数: 首先读取测试数据组数 T，然后循环读取每组数据的 a, b, c 和 P，判断序列是等差数列还是等比数列，并调用相应的函数计算第 P 项，最后输出结果。

总结

本文详细讲解了如何使用 C++ 代码判断一个序列是等差数列还是等比数列，并计算其第 P 项的值，同时针对大数结果进行了取模处理。代码简洁易懂，适合初学者学习。