64位整数乘法

求a乘b对p取模的值，\(1 \leq a, b, p\leq 10^{18}\)

因为a，b的范围到了\(10^{18}\)，相当于64位的整数，二者相乘之后就变成了128位的整数，计算机没有这么大的类型存储。虽然不能乘，但是我们可以想象成是b个a相加，将b写成二进制形式，那么答案就是\(a\times(2^{k_1}+2^{k_2}+...2^{k_n})\)

上代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
typedef unsigned long long ULL;
int main()
{
    ULL a, b, p;
    cin >> a >> b >> p;
    ULL res = 0;
    while(b)
    {
        if(b & 1) res = (res + a) % p;
        b >>= 1;
        a = a * 2 % p;
    }
    cout << res;
    return 0;
}

费解的开关

25盏灯排成一个 5×5 的方形，每一步，游戏者可以改变某一个灯的状态。游戏者改变一个灯的状态会产生连锁反应：和这个灯上下左右相邻的灯也要相应地改变其状态。我们用数字1表示一盏开着的灯，用数字0表示关着的灯。给定一些游戏的初始状态，编写程序判断游戏者是否可能在 6 步以内使所有的灯都变亮。

如果第一行的(i, j)位置是0，那么改变(i + 1, j)就可以让(i, j)变成1，但是如果就按题目给定的25盏灯进行上述操作，因为第一行是给定的，那么只会有一种结果，所以我们需要把第一行的所有情况都考虑到，第一行共有32种情况，我们不管第一行题目给的是什么样都直接把那32种情况都改变一遍，然后再判断 1~3 行改变第 2~4 行，最后判断第四行是不是全是开即可

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
56
57
58
59
60
61
62
63
#include <iostream>
#include <cstring>
using namespace std;
const int N = 510;
char g[N][N], cp[N][N];
int dx[5] = {0, 1, 0, -1, 0}, dy[5] = {1, 0, -1, 0, 0};//矢量，方便表示某个位置的上下左右和自己

void turn(int x, int y)//改变这个位置和其上下左右位置的状态
{
    for(int i = 0; i < 5; i++)
    {
        int a = x + dx[i], b = y + dy[i];
        if(a < 0 || a >= 5 || b < 0 || b >= 5) continue;
        g[a][b] ^= 1;
    }
}

int main()
{
    int n;
    cin >> n;
    while(n--)
    {
        for(int i = 0;i < 5; i++) cin >> g[i];
        int res = 10;//初始化答案，大于6即可
        for(int op = 0; op < 32; op++)//第一行的32种情况
        {
            int step = 0;
            memcpy(cp, g, sizeof(g));//拷贝一份
            for(int i = 0; i < 5; i++)//对第一行进行操作
            {
                if(op >> i & 1)//这个数的二进制哪一位是1就改变哪个位置的状态（不管它现在是什么状态） 
                {
                    step++;
                    turn(0, 4-i);
                }
            }
            for(int i = 0; i < 4; i++)//对2~4行进行操作
            {
                for(int j = 0; j < 5; j++)
                {
                    if(g[i][j] == '0')
                    //如果(i, j)是0，就改变(i + 1, j)
                    {
                        turn(i + 1, j);
                        step++;
                    }
                }
            }
            //判断最后一行是不是都是1
            bool dark = false;
            for(int i = 0; i < 5; i++)
            {
                if(g[4][i] == '0') dark = true;
            }
            if(!dark) res = min(res, step);
            memcpy(g, cp, sizeof(cp));//拷贝回来
        }
        if(res <= 6) cout << res << endl;
        else cout << -1 << endl;
    }
    return 0;
}