算法
(数学,二进制,位运算) $O(klogn)$
引理:当 $k \ge 2$ 时,$k^m \gt k^0 + k^1 + … + k^{m - 1}$。
证明:对 $m$ 由数学归纳法可证。
- 假设当 $m = m_0$ 时是正确的,那么当 $m = m_0 + 1$ 时:
- $k^{m_0 + 1} \ge k^{m_0} + k^{m_0} \gt k^0 + k^1 + … + k^{m_0 - 1} + k^{m_0}$
接下来将序列中的每个数,唯一映射到一个二进制数:
- 如果第 $i$ 个方幂存在,则二进制数的第 $i$ 位为1,否则为0。
由上述引理,序列中任意两数的大小关系,和映射成二进制数后的大小关系相同。
因此我们可以先求出第 $n$ 个二进制数,然后再反射出原数即可。
时间复杂度
先枚举 $n$ 的所有二进制位,再求出 $k$ 对应的方幂,一共两重循环,因此总时间复杂度是 $O(klogn)$。
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
LL get(int a, int b)
{
LL res = 1;
while (b -- ) res *= a;
return res;
}
int main()
{
int n, k;
cin >> k >> n;
LL res = 0;
for (int i = 0; i < 20; i ++ )
if (n >> i & 1)
res += get(k, i);
cout << res << endl;
return 0;
}
y总我这样为啥超时
快速幂版本