思路
递归
提取公因式,获得递推方程,分类讨论k的奇偶性
$\begin{split}
\small(p^{0} {\small+} p^{1} {\small+} \dots {\small+} p^{k})=sum(p,k/2)\cdot(1 + p^{k/2+ 1})
\end{split}$
递推型
- 前后关系:sum(n)与sum(n / 2)
- 子问题状态:k
- 递归结果:有返回值,局部变量
- 递归出口:k == 0
代码
#include <iostream>
#include <cmath>
using namespace std;
int sum(int p, int k)
{
if (k == 0) return 1;
if (k & 1) return sum(p, k / 2) * (1 + pow(p, k / 2 + 1));
else return sum(p, k - 1) * p + 1;
}
int main()
{
int p, k;
cin >> p >> k;
cout << sum(p, k) << endl;
}