算法
(数学,二进制,位运算) O(klogn)
引理：当 k≥2 时，km>k0+k1+…+km−1。
证明：对 m 由数学归纳法可证。
- 假设当 m=m0 时是正确的，那么当 m=m0+1 时:
- km0+1≥km0+km0>k0+k1+…+km0−1+km0
接下来将序列中的每个数，唯一映射到一个二进制数：
- 如果第 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;
}
/* 第2^i次方的位置放的是k^i k^(i+1)之间(共有2^i-1个数)的排布 最后一个一定是k^0+...+k^i 那么前面(2^i-2个数)是从k^0+k^1+...+k^(i-2)+k^i->k^0+k^1+...+k^(i-3)+k^(i-1)+k^i 即包含k^i 从k^0+...+k^(i-1)中倒序删掉一个后的序列 k^0+...+k^(i-2) -> k^0+k^1+...+k^(i-3)+k^(i-1) -> k^0+k^1+...+k^(i-4)+k^(i-2)+k^(i-1) */ #include<iostream> #include<algorithm> #include<cstring> using namespace std; int k,n; int qmi(int a,int b) { int res = 1; while(b) { if(b%2)res*=a; a*=a; b>>=1; } return res; } int main() { cin >> k >> n; int mi=0,tmp=n; while(tmp) { mi++; tmp>>=1; } mi--; int m = qmi(2,mi); // 如果是2的mi幂次个 直接输出k的i次方 if(n-m==0)cout << qmi(k,mi); // 否则 先找到比n小的2^mi 则n-2^mi后的第j个代表 k^0+...+k^mi 后减去k^(mi-j)(j共有i-1个) else { int misum = 1*(1-qmi(k,mi+1))/(1-k); int j = n-m; // cout << misum << " " << j << " " << mi << endl; cout << misum - qmi(k,mi - j); } return 0; }y总我这样为啥超时
#include<iostream> #include<algorithm> using namespace std; int k, N; int main() { cin >> k >> N; int res = 0, t = 1; while (N) { if (N & 1) res += t; t *= k; N >>= 1; } cout << res << endl; return 0; }快速幂版本