A - a^b

A - a^b

​思路：

快速幂 + 龟速乘

数据范围为：$1e18$ 次方。
long long 范围为 $1e18$
即、两数据相乘也会溢出，用龟速乘化乘法为加法

代码如下：

//#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1000010, null = 0x3f3f3f3f;
//const int mod = 1e9 + 7;
const double eps = 1e-8;

int n, m, mod;

int qmadd(int a, int k, int p)
{
    int res = 0;
    while(k)
    {
        if(k & 1) res = (res + a) % p;
        k >>= 1;
        a = (a + a) % p;
    }
    return res;
}

int qmi(int a, int k, int p)
{
    int res = 1;
    while(k)
    {
        if(k & 1) res = qmadd(res, a, p);
        k >>= 1;
        a = qmadd(a, a, p);
    }
    return res;
}

signed main()
{
    //fast;
    
    while(cin >> n >> m >> mod)
        cout << qmi(n ,m, mod) << endl;
    
    
    return 0;
}
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

---

B - Mocha and Math

B - Mocha and Math

思路：

通过无限次的交换，数组中的任何数可以与其他任何数 进行 & 操作，如此我们仅需判断，数组中的每一个数中的每一位是否有 $0$ 存在，若存在则答案的这位为 $0$
如此操作（将所有数&得出答案）即可得出最小的答案。

代码如下：

//#include 
#include 
#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1000010, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

void solve()
{
    int n;
    cin >> n;
    
    int res, x;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> x;
        if(i == 1) res = x;
        else res &= x;
    }
    cout << res << endl;
    
    return;
}

signed main()
{
    fast;
    int T; cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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

---

C - 高低位交换

C - 高低位交换

思路：

数据范围为：2^32次方
用 $unsignedint$ 保存数据
位运算的 移位操作 ( $>>$) 实现题目的高低位互换，或 ( $|$ ) 操作 实现高低位拼接到一起

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int unsigned int

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1000010, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

void solve()
{
    int n, res;
    cin >> n;
    
    res = (n >> 16)|(n << 16);
    
    cout << res << endl;
    
    return;
}

signed main()
{
    fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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

也可以用 $bitset$ ，不过麻烦一点

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int long long

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1000010, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

void solve()
{
    int n;
    cin >> n;
    bitset<32> s, t(n);
    
    for (int i = 0; i < 16; i ++ )
        s[i] = t[i + 16];
    for (int i = 16; i < 32; i ++ )
        s[i] = t[i - 16];
    
    int res = 0;
    int tt = 1;
    for (int i = 0; i < 32; i ++ )
    {
        if(s[i]) res += tt;
        tt *= 2;
    }
    
    cout << res << endl;
    
    return;
}

signed main()
{
    fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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

---

D - 前缀异或

D - 前缀异或

思路：

前缀异或和
$[l,r]$ $=$ a[l] ^ a[l+1] …… ^ a[r] = s[r] ^ s[l-1]
如图：（相同抵消）

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int unsigned int

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1000010, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

void solve()
{
    int n;
    cin >> n;
    int a[N];
    
    a[0] = 0;
    int x;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> x;
        a[i] = a[i - 1] ^ x;
    }
    
    int m;
    cin >> m;
    while(m -- )
    {
        int l, r;
        cin >> l >> r;
        cout << (a[r] ^ a[l - 1]) << endl;
    }
    
    return;
}

signed main()
{
    fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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

---

E - 一个奇数次

E - 一个奇数次

思路：

数字偶数次，异或操作( ^ ) 中偶数次的数相抵消

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int unsigned int

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e9+10, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

void solve()
{
    int n;
    cin >> n;
    
    int res = 0, x;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> x;
        res ^= x;
    }
    
    cout << res << endl;
    
    return;
}

signed main()
{
    fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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

---

F - 二个奇数次

F - 二个奇数次

思路：

• 先全部异或一遍，答案 $res$ 为两答案的异或值
• 再找到 $lowbit(res)$ 即所求两个数字的最低位的不同点
• 根据答案的不同点分开异或一边，使两答案分别异或到两个值中

代码如下：

#include 

#define fast ios::sync_with_stdio(false), cin.tie(nullptr); cout.tie(nullptr)

#define x first
#define y second
#define int unsigned int

using namespace std;

typedef pair<int, int> PII;

const int N = 1e6 + 10, M = 1e9+10, null = 0x3f3f3f3f;
const int mod = 1e9 + 7;
const double eps = 1e-8;

void solve()
{
    int n;
    cin >> n;
    
    int nums[N];
    int res = 0, x;
    for (int i = 1; i <= n; i ++ )
    {
        cin >> nums[i];
        res ^= nums[i];
    }
    
    int lowbit = res & (-res);
    
    int a = 0, b = 0;
    for (int i = 1; i <= n; i ++ )
    {
        if(nums[i] & lowbit) a ^= nums[i];
        else b ^= nums[i];
            
    }
    
    cout << min(a, b) << " " << max(a, b) << endl;
    
    return;
}

signed main()
{
    fast;
    int T = 1; 
    //cin >> T;
    while(T -- )
        solve();
    
    return 0;
}
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