64位整数乘法（龟速乘）

题意

求a*b mod p的值。

1≤a,b,p≤10e18

思考

龟速乘用加法来模拟乘法，时间复杂度log(n)，好处是不用写高精度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>

using namespace std;
typedef long long LL;
LL a,b,p;

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

费解的开关(递推)

题意

5*5的矩形，0表示灭，1表示开。每次改变十字形的灯的状态。

给定一个初始状态，判断最少按多少次全部变成1。如果大于6次，输出-1。

500组测试数据。

思考

方法一：dfs搜索状态

方法二：递推

  • 每个灯最多按一次
  • 按的顺序没有影响
  • 当第 i 行开关锁死后，第 i+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
56
57
58
59
60
61
#include<bits/stdc++.h>

using namespace std;

char a[10][10];
char b[10][10];
int t;
int ans,cnt;
char val(char x){
    if(x=='0') return '1';
    else return '0';
}

int fun(){
    for(int i=0;i<4;i++){
        for(int j=0;j<5;j++){
            if(b[i][j]=='0'){
                cnt++;
                b[i][j] = val(b[i][j]);
                b[i+1][j] = val(b[i+1][j]);
                if(j-1 >= 0) b[i+1][j-1] = val(b[i+1][j-1]);
                if(j+1 < 5)  b[i+1][j+1] = val(b[i+1][j+1]);
                if(i+2<5) b[i+2][j] = val(b[i+2][j]);
            }
        }
    }
    for(int i=0;i<5;i++){
        if(b[4][i]=='0') return 0x3f3f3f3f;
    }

    return cnt;
}
int main(){
    scanf("%d",&t);
    while(t--){
        ans=0x3f3f3f3f;
        for(int i=0;i<5;i++){
            scanf("%s",a[i]);
        }
        for(int i=0;i<=31;i++){
            cnt=0;
            memcpy(b,a,sizeof b);
            for(int j=0;j<5;j++){
                if(1&(i>>j)){
                    b[0][j] = val(b[0][j]);
                    b[1][j] = val(b[1][j]);
                    if(j-1 >= 0) b[0][j-1] = val(b[0][j-1]);
                    if(j+1 < 5)  b[0][j+1] = val(b[0][j+1]);
                    cnt++;
                }
            }
            ans = min(ans,fun()); 
        }
        if(ans==0x3f3f3f3f||ans>6){
            puts("-1");
        }else{
            printf("%d\n",ans);
        }
    }
    return 0;
}

总结

一行一行的推

约数之和（分治+递归）

题意

假设现在有两个自然数 $A$ 和 $B, S$ 是 $A^{B}$ 的所有约数之和。 请你求出 $S \bmod 9901$ 的值是多少。

思考

这里实现一个sum函数, $\operatorname{sum}(\mathrm{p}, \mathrm{k})$ 表示 $p^{0}+p^{1}+\ldots+p^{k-1}$
思路, 当 $k$ 为偶数时, sum $(p, k)$ 可以拆解成

即

也就是

进一步化简

当 $k$ 为奇数时, 为了更方便调用我们写的偶数项情况, 可以单独拿出最后一项, 把剩下的项转化为求偶数项 的情况来考虑, 再加上最后一项, 就是奇数项的情况了。也即sum $(p, k-1)+p^{k-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
#include <cstdio>

const int mod = 9901;

int qmi(int a, int k)
{
    int res = 1;
    a %= mod;
    while (k)
    {
        if (k & 1) res = res * a % mod;
        a = a * a % mod;
        k >>= 1;
    }
    return res;
}

int sum(int p, int k)
{
    if (k == 1) return 1;
    if (k % 2 == 0) return (1 + qmi(p, k / 2)) * sum(p, k / 2) % mod;
    return (sum(p, k - 1) + qmi(p, k - 1)) % mod;
}

int main()
{
    int a, b;
    scanf("%d%d", &a, &b);

    int res = 1;
    // 对a分解质因数
    for (int i = 2; i * i <= a; i ++ )
        if (a % i == 0)
        {
            int s = 0;
            while (a % i == 0)
            {
                a /= i, s ++ ;
            }
            res = res * sum(i, b * s + 1) % mod;
        }

    if (a > 1) res = res * sum(a, b + 1) % mod;
    if (a == 0) res = 0;

    printf("%d\n", res);

    return 0;
}

总结

等比数列模q求和的常用做法

分形之城(分治)

题意

见网页

思考

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
#include <iostream>
#include <cmath>
#define x first
#define y second
using namespace std;
typedef long long LL;
typedef pair<LL, LL> PLL;

PLL calc(LL n, LL m) {
    if(n == 0) return {0, 0};
    LL len = 1ll << (n - 1); // n - 1级图构成n级图平移时的单位长度
    LL cnt = 1ll << (n - 1) * 2; // n - 1级图中所含的元素个数
    LL cnk = m / cnt; // 在n级图中，编号为m的元素所属块的编号
    LL idx = m % cnt; // 在n级图中，编号为m的元素在所属块中的编号
    PLL pos = calc(n - 1, idx); // 在n级图中，编号为m的元素在所属块中的坐标
    LL x = pos.x, y = pos.y;
    // 根据n级图中某个块的编号和这个块中某个元素的坐标，确定n - 1级图的坐标变换
    // 注意：离散坐标系跟实数坐标系有些许差别，不考虑这些差别
    // 结果必然是抓耳挠腮。hh
    if(cnk == 0) return {y, x}; // 没有平移，虽是旋转，坐标关系容易确定
    if(cnk == 1) return {x, y + len}; // 单纯平移
    if(cnk == 2) return {x + len, y + len}; // 单纯平移
    if(cnk == 3) return {len * 2 - y - 1, len - x - 1}; // 旋转又平移
}

LL rounding(double a) {
    LL b;
    if(a > 0) b = (a * 2 + 1) / 2;
    else b = (a * 2 - 1) / 2;  
    return b;
}

int main() {
    int times;
    cin >> times;
    while(times--) {
        LL n, a, b;
        cin >> n >> a >> b;
        PLL pa = calc(n, a - 1);
        PLL pb = calc(n, b - 1);
        //double x = pa.x - pb.x, y = pa.y - pb.y;
        //printf("%.0lf\n", sqrt(x * x + y * y) * 10.00);
        LL x = pa.x - pb.x, y = pa.y - pb.y;
        double dist = sqrt(x * x + y * y);
        cout << rounding(dist) << endl;
    }
    return 0;
}