154 lines
4.0 KiB
Markdown
154 lines
4.0 KiB
Markdown
##[$AcWing$ $1289$. 序列的第$K$个数](https://www.acwing.com/problem/content/1291/)
|
||
|
||
### 一、题目描述
|
||
$BSNY$ 在学等差数列和等比数列，当已知前三项时，就可以知道是等差数列还是等比数列。
|
||
|
||
现在给你 **整数** 序列的前三项，这个序列要么是等差序列，要么是等比序列，你能求出第 $k$ 项的值吗?
|
||
|
||
如果第 $k$ 项的值太大，对其取模 $200907$。
|
||
|
||
**输入格式**
|
||
第一行一个整数 $T$，表示有 $T$ 组测试数据；
|
||
|
||
对于每组测试数据，输入前三项 $a,b,c$，然后输入 $k$。
|
||
|
||
**输出格式**
|
||
对于每组数据，输出第 $k$ 项取模 $200907$ 的值。
|
||
|
||
**数据范围**
|
||
$1≤T≤100$
|
||
$1≤a≤b≤c≤10^9$
|
||
$1≤k≤10^9$
|
||
|
||
**输入样例**
|
||
```cpp {.line-numbers}
|
||
2
|
||
1 2 3 5
|
||
1 2 4 5
|
||
```
|
||
**输出样例**
|
||
```cpp {.line-numbers}
|
||
5
|
||
16
|
||
```
|
||
|
||
### 二、$Q$：一个数列能不能即是等差数列又是等比数列?
|
||
|
||
#### 结论：一个数列如果是即是等差又是等比，那么它必然是一个全等数列
|
||
|
||
**证明**：
|
||
设三个连续数字$a\ b \ c$,
|
||
等差数列，所以$a+c=2b$ ①
|
||
等比数列，所以$\frac{b}{a}=\frac{c}{b}$,所以$b^2=ac$ ②
|
||
|
||
将$a=2b-c$代入②
|
||
$b^2=(2b-c)*c$
|
||
$b^2=2bc-c^2$
|
||
$b^2-2bc+c^2=0$
|
||
$(b-c)^2=0$
|
||
∴$b=c$
|
||
|
||
由此可知，题目中给了数列的前三项，存在可能即是等差又是等比的情况，但此时就是一个全等数列，按哪个规则进行计算都是一样的结果，题目不缺少条件。
|
||
|
||
### 三、题意分析
|
||
|
||
* **等差数列**
|
||
公差 $d=b-a$
|
||
第$1$项,$a+0*d$
|
||
第$2$项,$a+1*d$
|
||
第$3$项,$a+2*d$
|
||
...
|
||
第$k$项，应该是$a+(k-1)d$，这个很好求，直接求然后注意取模就行了。
|
||
|
||
* **等比数列**
|
||
公比$p=\frac{b}{a}$
|
||
第$1$项,$a*p^0$
|
||
第$2$项,$a*p^1$
|
||
第$3$项,$a*p^2$
|
||
...
|
||
第$k$项,$a*p^{k-1}=a*(\frac{b}{a})^{k-1}$
|
||
|
||
这东西用 **快速幂** 就行了
|
||
|
||
### 四、理解与思考
|
||
数学的题，一般不会真的用代码去暴力计算，通常是推公式，证明。在完成公式的推导后，再用代码进行简单计算，比如$2022$ $CSP-J$的第二题就是一道公式的推导题，小心下细节就行了。
|
||
|
||
- **快速幂**:把次数依次化为$2$进制，即可迭代
|
||
- **龟速乘**:把当前数变为$2$进制加起来，用于数据很大的情况
|
||
|
||
### 五、实现代码
|
||
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
const int MOD = 200907;
|
||
|
||
// 快速幂
|
||
int qmi(int a, int b) {
|
||
int res = 1;
|
||
while (b) {
|
||
if (b & 1) res = res * a % MOD;
|
||
a = a * a % MOD;
|
||
b >>= 1;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
signed 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) * (k - 1)) % MOD << endl; // 这个比较简单
|
||
else // 等比
|
||
cout << a * qmi(b / a, k - 1) % MOD << endl; // 这个需要快速幂
|
||
}
|
||
}
|
||
```
|
||
|
||
### 六、龟速乘版本
|
||
```cpp {.line-numbers}
|
||
#include <bits/stdc++.h>
|
||
using namespace std;
|
||
#define int long long
|
||
|
||
const int MOD = 200907;
|
||
|
||
// 龟速乘，快速加
|
||
int qadd(int a, int b) {
|
||
int res = 0;
|
||
while (b) {
|
||
if (b & 1) res = (res + a) % MOD;
|
||
b >>= 1;
|
||
a = (a + a) % MOD;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
// 快速幂
|
||
int qmi(int a, int b) {
|
||
int res = 1;
|
||
while (b) {
|
||
if (b & 1) res = (res * a) % MOD;
|
||
b >>= 1;
|
||
a = a * a % MOD;
|
||
}
|
||
return res;
|
||
}
|
||
|
||
signed main() {
|
||
int T;
|
||
cin >> T;
|
||
while (T--) {
|
||
int a, b, c, k;
|
||
cin >> a >> b >> c >> k;
|
||
if (a + c == b + b)
|
||
cout << (qadd(b - a, k - 1) + a) % MOD << endl; // 为等差即套公式，首项+公差*（项数-1）
|
||
else
|
||
cout << qmi(b / a, k - 1) * a % MOD << endl; // 等比数列用快速幂算末项
|
||
}
|
||
}
|
||
``` |