【每日一题29】AcWing 428. 数列

发表于 更新于 分类于 Valine：
本文字数： 148 阅读时长 ≈ 1 分钟

Day29 AcWing 428. 数列

思路

  1. 二进制映射
  2. 位运算
    算法
    将序列中的每个数，唯一映射到一个二进制数：
  • 如果第 $i$ 个方幂存在，则二进制位的第 $i$ 位为1，否则为0
    由上述引理，序列中任意两数的大小关系，和映射成二进制数后的大小关系相同。
    因此我们可以先求出第 $n$ 个二进制数，然后再反射出原数即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#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;
}