题目描述
BSNY在学等差数列和等比数列,当已知前三项时,就可以知道是等差数列还是等比数列。现在给你序列的前三项,这个序列要么是等差序列,要么是等比序列,你能求出第k项的值吗。如果第k项的值太大,对200907取模。
输入描述:
第一行一个整数T,表示有T组测试数据;
对于每组测试数据,输入前三项a,b,c,然后输入k。
输出描述:
对于每组数据输出第k项的值,对200907取模。
思路:
一看题目就知道使用快速幂了,不多解释了。
什么是快速幂与时间复杂度分析:
快速幂是一种简化运算底数的n次幂的算法,理论上其时间复杂度为 O(log₂N),而一般的朴素算法则需要O(N)的时间复杂度。简单来说快速幂其实就是抽取了指数中的2的n次幂,将其转换为时间复杂度为O(1)的二进制移位运算,所以相应地,时间复杂度降低为O(log₂N)。
代码原理:
以a^13为例,
先把指数13化为二进制就是1101,把二进制数字1101直观地表现为十进制则是如下的等式:
13 = 1 * (2^3) + 1 * (2^2) + 0 * (2^ 1) + 1 * (2^0)
这样一来a^13可以如下算出:
a^13 = a ^ (2^3) * a ^ (2^2) * a ^ (2^0)
完整C++版AC代码:
#include <iostream> using namespace std; typedef long long ll; ll mod = 200907; ll ksm(ll a,ll b,ll p) { ll ans = 1; while (b) { if (b & 1) { ans = ans * a % p; } b = b >> 1; a = a * a % p; } return ans; } int main() { int t; cin >> t; while (t--) { ll a, b, c; int k; cin >> a >> b >> c >> k; if (b - a == c - b) {//等差序列 int r = b - a; cout << (a % mod + (c - b) * (k - 1) % mod) % mod << endl; } else { cout << (a % mod * ksm(c / b, k - 1, mod)) % mod << endl; } } return 0; }