a^b（位运算、快速幂思想）

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
//https://www.acwing.com/problem/content/91/

#include <iostream>

using namespace std;

int main()
{
    long long a, b, p;
    long long ans;
    
    cin >> a >> b >> p;
    
    ans = 1 % p;
    while(b)
    {
        if(b & 1)   ans = (ans * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    
    cout << ans << endl;
    
    return 0;
}

答案要求输出a^b%p。根据题目给出的范围，无法使用朴素做法。

可以将b转换成k位二进制表示形式，其中$k = \lceil {ln{(b+1)}} \rceil$。

$b = c_{k-1}2^{k-1} + … + c_{0}2^{0}$

$a^b = a^{c_{k-1}2^{k-1}} * … * a^{c_{0}2^{0}}$

ci表示b的第i位，有两种取值：0或1。

若b的第i位为1，则将$a^{2^{k-1}}$累乘到答案中。

又因为：$a^{2^i} = a^{2^{i-1}} * a^{2^{i-1}}$

我们使用a表示底数，每次计算后a = (a * a) % p。

所以我们只需要依次取b的每一位二进制数，若为1，则将a累乘到答案中。

注意：ans = 1 % p 而不是 1，是因为考虑到p = 1的特殊情况。

64位整数乘法（位运算、快速幂思想）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//https://www.acwing.com/problem/content/92/
#include <iostream>

using namespace std;

typedef long long LL;

int main()
{
    LL a, b, p;
    LL ans = 0;
    
    cin >> a >> b >> p;
    while(b)
    {
        if(b & 1)   ans = (ans % p + a % p) % p;
        a = 2 * a % p;
        b >>= 1;
    }
    
    cout << ans << endl;
    
    return 0;
}

答案要求输出a*b%p，其中a，b，p数量级均为long long级别。

利用快速幂的思想，将b使用二进制表示：$b = c_{k - 1}2^{k-1} + … + c_02^0$。

则$a*b = a * c_{k - 1}2^{k-1} + … + a * c_02^0$，其中$c_i$表示b二进制形式的第i位：0或1。

并且，可以递推得到$a*2^{k} = 2 * a * 2^{k-1}$。

我们使用a表示基数，每次计算后a = 2 * a。

然后依次分解b的每一位二进制数，若为1，则将计算结果累加到答案中。

起床困难综合征（位运算）

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//https://www.acwing.com/problem/content/1000/
#include <iostream>

using namespace std;

typedef pair<string, int> PII;

const int N = 1e5 + 10;

int n, m;
int k;
PII cmd[N];

//循环n次，计算第bit位进行位运算后的结果。
int calc(int bit, int a)
{
    for(int i = 0; i < k; i++)
    {
        if(cmd[i].first == "AND")       a &= ((cmd[i].second >> bit) & 1);
        else if(cmd[i].first == "OR")   a |= ((cmd[i].second >> bit) & 1);
        else                            a ^= ((cmd[i].second >> bit) & 1);
    }
    
    return a;
}

int main()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
    {
        string str;
        int num;
        
        cin >> str >> num;
        cmd[k++] = make_pair(str, num);
    }
    
    //1.不超过m
    //2.判定1还是0比较好
    int val = 0, ans = 0;
    for(int i = 30; i >= 0; i--)
    {
        int res0 = calc(i, 0);
        int res1 = calc(i, 1);
        
        
        if(val + (1 << i) <= m && res1 > res0)  val += 1 << i, ans += 1 << i;
        else ans += res0 << i;
    }
    
    cout << ans << endl;
    
    return 0;
}

题目给出n个位运算，要求出对任意[0, m]范围内的数，按题目要求进行位运算结果的最大值。

位运算的特点是没有进位，只影响进行运算的位。

我们使用pair保存指令，然后从最高位开始逐个考虑ans的每一位应该填的数字。

若该位填1，需满足以下条件：

  1. 该位填1后数值不超过m，否则填0。
  2. 进行位运算后，该位应该为1。否则填0。

res0表示第i位填0后该位进行位运算的结果，res1则表示第i位填1后该位进行位运算的结果。