AcWing 1289. 序列的第k个数(快速幂)

2024-01-09 07:26:58

题目链接

活动 - AcWing 本课程系统讲解常用算法与数据结构的应用方式与技巧。icon-default.png?t=N7T8https://www.acwing.com/problem/content/1291/

题解

可以证明,当本题中的数列既是等差数列又是等比数列的时候,该数列只能为全等数列。若本题中的数列为等比数列,则公比q不是分数,若是分数,无法满足该数列为整数序列的条件。

代码

#include <cstring>
#include <iostream>
#include <algorithm>

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;
    cin >> n;
    while (n--)
    {
        int a, b, c, k;
        cin >> a >> b >> c >> k;
        if (a + c == b * 2) cout << (a + (b - a) * (LL)(k - 1)) % mod << endl;
        else cout << (LL)a * qmi(b / a, k - 1) % mod << endl;
    }
    
    return 0;
}

参考资料

  1. AcWing算法提高课

文章来源:https://blog.csdn.net/u012181348/article/details/135468913
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。