AcWing 1289. 序列的第k个数（快速幂）

题目链接

活动 - AcWing 本课程系统讲解常用算法与数据结构的应用方式与技巧。https://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算法提高课