1
//求出n位格雷码中的k号二进制串。
2
#include <bits/stdc++.h>
3
using namespace std;
4

5
typedef unsigned long long ull;
6

7
string f(int n, int k)
8
{
9
    if (n == 0) // 位数是0的边界情况
10
        return "";
11

12
    if (k < (1ull << n - 1))
13
        return "0" + f(n - 1, k);
14

15
    else
16
    {
17
        ull t = (1ull << n) - 1;
18

19
        if (n == 64) // 特判n=64的情况
20
            t = -1; // t的二进制表示是64个1
21
        return "1" + f(n - 1, t - k);
22
    }
23
}
24

25
int main()
26
{
27
    int n;
28
    ull k;
29
    cin >> n >> k;
30

31
    cout << f(n, k) << endl;
32
    return 0;
33
}

1
int grey(int n) { return n ^ (n >> 1); }

1
// Problem: 线性同余方程
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/880/
4
// Time: 2026-02-12 21:35:01
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <bits/stdc++.h>
7
using namespace std;
8

9
int exgcd(int a, int b, int &x, int &y)
10
{
11
    if (b == 0) // 边界情况
12
    {
13
        x = 1, y = 0;
14
        return a;
15
    }
16

17
    int d = exgcd(b, a % b, y, x);
18
    y -= a / b * x;
19
    return d;
20
}
21

22
int main()
23
{
24
    int n;
25
    cin >> n;
26

27
    while (n--)
28
    {
29
        int a, b, m;
30
        cin >> a >> b >> m;
31

32
        int x, y;
33
        int d = exgcd(a, m, x, y);
34

35
        if (b % d)
36
            puts("impossible");
37
        else
38
            cout << (long long) b / d * x % m << endl;
39
    }
40
    return 0;
41
}

1
// Problem: 表达整数的奇怪方式
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/206/
4
// Time: 2026-03-19 23:02:27
5
#include <bits/stdc++.h>
6
using namespace std;
7
typedef long long LL;
8

9
LL exgcd(LL a, LL b, LL &x, LL &y)
10
{
11
    if (!b)
12
    {
13
        x = 1, y = 0;
14
        return a;
15
    }
16

17
    LL d = exgcd(b, a % b, y, x);
18
    y -= a / b * x;
19
    return d;
20
}
21

22

23
int main()
24
{
25
    int n;
26
    cin >> n;
27

28
    LL x = 0, m1, a1;
29
    cin >> m1 >> a1;
30
    for (int i = 0; i < n - 1; i++)
31
    {
32
        LL m2, a2;
33
        cin >> m2 >> a2;
34
        LL k1, k2;
35
        LL d = exgcd(m1, m2, k1, k2);
36
        if ((a2 - a1) % d)
37
        {
38
            x = -1;
39
            break;
40
        }
41

42
        k1 *= (a2 - a1) / d;
43
        k1 = (k1 % (m2 / d) + m2 / d) % (m2 / d);
44

45
        x = k1 * m1 + a1;
46

47
        LL m = abs(m1 / d * m2);
48
        a1 = k1 * m1 + a1;
49
        m1 = m;
50
    }
51

52
    if (x != -1)
53
        x = (a1 % m1 + m1) % m1;
54

55
    cout << x << endl;
56

57
    return 0;
58
}

1
#include <algorithm>
2
#include <iostream>
3
using namespace std;
4
const int N = 1000010;
5

6
int primes[N], cnt; // primes数组用来存放质数
7
bool st[N]; // st[i] = true表示被筛了
8

9
void get_primes(int n)
10
{
11
    for (int i = 2; i <= n; i++)
12
    {
13
        if (!st[i])
14
            primes[cnt++] = i;
15

16
        for (int j = i + i; j <= n; j += i)
17
            st[j] = true;
18
    }
19
}
20

21
int main()
22
{
23
    int n;
24
    cin >> n;
25

26
    get_primes(n);
27

28
    cout << cnt << endl;
29

30
    return 0;
31
}

1
// Problem: 筛质数
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/870/
4
// Time: 2026-02-06 20:36:05
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <algorithm>
7
#include <iostream>
8
using namespace std;
9
const int N = 1000010;
10

11
int primes[N], cnt; // primes数组用来存放质数
12
bool st[N]; // st[i] = true表示被筛了
13

14
void get_primes(int n)
15
{
16
    for (int i = 2; i <= n; i++)
17
    {
18
        if (!st[i])
19
        {
20
            primes[cnt++] = i;
21
            for (int j = i + i; j <= n; j += i)
22
                st[j] = true;
23
        }
24
    }
25
}
26

27
int main()
28
{
29
    int n;
30
    cin >> n;
31

32
    get_primes(n);
33

34
    cout << cnt << endl;
35

36
    return 0;
37
}

1
// Problem: 筛质数
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/870/
4
// Time: 2026-02-06 20:36:05
5
// Powered by CP Editor (https://cpeditor.org)
6
#include <algorithm>
7
#include <iostream>
8
using namespace std;
9
const int N = 1000010;
10

11
int primes[N], cnt; // primes数组用来存放质数
12
bool st[N]; // st[i] = true表示被筛了
13

14
void get_primes(int n)
15
{
16
    for (int i = 2; i <= n; i++)
17
    {
18
        if (!st[i])
19
            primes[cnt++] = i;
20

21
        for (int j = 0; primes[j] <= n / i; j++) // primes[j] * i <= n，此处防止爆数据
22
        {
23
            st[primes[j] * i] = true;
24
            // 把当前的所有质数和i的乘积都筛掉
25
            // 因为primes[j]是从小到大枚举的
26
            // 所以primes[j]一定是i的最小质因子
27

28
            if (i % primes[j] == 0)
29
                break;
30
            // i乘上其他质数的结果一定会在后面被primes[j]的倍数通过乘上最小质因子的方式筛掉
31
            // 就不需要在这里先筛一次了，直接break
32
        }
33
    }
34
}
35

36
int main()
37
{
38
    int n;
39
    cin >> n;
40

41
    get_primes(n);
42

43
    cout << cnt << endl;
44

45
    return 0;
46
}

1
// Problem: 欧拉函数
2
// Contest: AcWing
3
// URL: https://www.acwing.com/problem/content/875/
4
// Time: 2026-02-10 17:34:30
5
//
6
// Powered by CP Editor (https://cpeditor.org)
7
#include <bits/stdc++.h>
8
using namespace std;
9

10
int main()
11
{
12
    int n;
13
    cin >> n;
14

15
    while (n--)
16
    {
17
        int a;
18
        cin >> a;
19

20
        int res = a; // 求解公式前面的n
21

22
        for (int i = 2; i <= a / i; i++) // 分解质因数
23
        {
24
            if (a % i == 0)
25
            {
26
                // 求解公式的等价写法，防止运算的时候出现小数
27
                res = res / i * (i - 1);
28
                while (a % i == 0)
29
                    a /= i;
30
            }
31
        }
32

33
        if (a > 1) // 剩余的那个因数
34
            res = res / a * (a - 1);
35

36
        cout << res << endl;
37
    }
38

39
    return 0;
40
}