最大公约数

GitHub 跳转原题关系图返回列表

把第 t 天的值看成目标点周围曼哈顿半径 t 菱形区域的 gcd，再按目标值的质因子求最早被周围格子消掉的时间。

OJ: luogu

题目 ID: P7243

难度:提高+/省选-

标签:数学最大公约数思维曼哈顿距离Pollard Rho

日期: 2026-06-19 08:34

题意

有一个 n × m 的矩阵。

一次变换会把每个位置 (i,j) 改成：

自己；
上下左右存在的格子；

这些数的最大公约数。

现在只问一个位置 (x,y)：它最少经过多少次变换会变成 1。

如果无论怎么变都不可能变成 1，输出 -1。

思路

最直接的想法是按天模拟整张矩阵。

这个版本最容易理解题意：

cpp

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
64
65
66
67
68
69
70
71
72#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;

const int MAXN = 15;

int n, m;
ull cur[MAXN][MAXN], nxt[MAXN][MAXN];
int target_x, target_y;
int dx[5] = {0, -1, 1, 0, 0};
int dy[5] = {0, 0, 0, -1, 1};

bool in_board(int x, int y) {
    return x >= 1 && x <= n && y >= 1 && y <= m;
}

// 模拟一天，并返回矩阵是否真的发生了变化。
bool transform_once() {
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            ull g = cur[i][j];
            for (int k = 1; k <= 4; k++) {
                int nx = i + dx[k];
                int ny = j + dy[k];
                if (in_board(nx, ny)) {
                    g = gcd(g, cur[nx][ny]);
                }
            }
            nxt[i][j] = g;
        }
    }

    bool changed = false;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (cur[i][j] != nxt[i][j]) {
                changed = true;
            }
            cur[i][j] = nxt[i][j];
        }
    }
    return changed;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> cur[i][j];
        }
    }
    cin >> target_x >> target_y;

    // 曼哈顿半径超过整个棋盘后，答案就不会再变化了。
    for (int day = 0; day <= n + m; day++) {
        if (cur[target_x][target_y] == 1) {
            cout << day << '\n';
            return 0;
        }

        if (!transform_once()) {
            break;
        }
    }
    cout << -1 << '\n';

    return 0;
}

但这题的数据范围很大，不能真的一天一天推。

第 t 天对应一个曼哈顿菱形

先看第 1 天，目标点 (x,y) 取的是：

自己；
上下左右。

这正是一个曼哈顿距离不超过 1 的区域。

再看第 2 天，它取的是这几个点第 1 天结果的 gcd。由于 gcd 具有结合律和交换律，所以最终等价于把更大一圈的初始格子全部一起取 gcd。

继续归纳下去，可以得到：

第 t 天时，(x,y) 的值等于所有满足

|i-x| + |j-y| <= t

的初始格子的整体 gcd。

只需要关心目标值的质因子

设目标点初始值是 v = a[x][y]。

以后每一天的值都只会不断变小，所以它的质因子只会消失，不可能新出现。

因此我们只需要关心 v 的不同质因子。

设其中一个质因子是 p。

如果半径 t 的菱形里所有数都还能被 p 整除，那么第 t 天后的 gcd 里还会保留 p。

反过来，只要这个菱形里出现了一个不能被 p 整除的格子，那么 p 就被消掉了。

所以对于每个质因子 p，只要求出：

离 (x,y) 最近的、满足 a[i][j] % p != 0 的格子的曼哈顿距离 d_p。

那么：

当 t < d_p 时，p 还在；
当 t >= d_p 时，p 已经消失。

最终值要变成 1，就要求所有质因子都消失。

所以答案就是：

所有 d_p 的最大值。

如果某个质因子在整张矩阵里都找不到“不能整除它”的格子，那么它永远不会消失，答案就是 -1。

为什么要用 Pollard Rho

因为 a[i][j] 最大可达 10^18，而我们只需要分解目标点 a[x][y] 的质因子。

这个范围下，用 Miller Rabin + Pollard Rho 提取不同质因子是比较稳妥的做法。

代码

cpp

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158#include <bits/stdc++.h>
using namespace std;

using ull = unsigned long long;
using u128 = __uint128_t;

const int MAXN = 2005;

int n, m;
ull a[MAXN][MAXN];
int target_x, target_y;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

ull mul_mod(ull a, ull b, ull mod) {
    return (u128) a * b % mod;
}

ull pow_mod(ull a, ull b, ull mod) {
    ull res = 1;
    while (b) {
        if (b & 1) {
            res = mul_mod(res, a, mod);
        }
        a = mul_mod(a, a, mod);
        b >>= 1;
    }
    return res;
}

bool miller_rabin(ull n) {
    if (n < 2) {
        return false;
    }
    for (ull p : {2ULL, 3ULL, 5ULL, 7ULL, 11ULL, 13ULL, 17ULL, 19ULL, 23ULL, 29ULL, 31ULL, 37ULL}) {
        if (n % p == 0) {
            return n == p;
        }
    }

    ull d = n - 1;
    int s = 0;
    while ((d & 1) == 0) {
        d >>= 1;
        s++;
    }

    for (ull a : {2ULL, 325ULL, 9375ULL, 28178ULL, 450775ULL, 9780504ULL, 1795265022ULL}) {
        if (a % n == 0) {
            continue;
        }
        ull x = pow_mod(a, d, n);
        if (x == 1 || x == n - 1) {
            continue;
        }

        bool ok = false;
        for (int r = 1; r < s; r++) {
            x = mul_mod(x, x, n);
            if (x == n - 1) {
                ok = true;
                break;
            }
        }
        if (!ok) {
            return false;
        }
    }
    return true;
}

ull pollard_rho(ull n) {
    if (n % 2 == 0) {
        return 2;
    }

    while (true) {
        ull c = uniform_int_distribution<ull>(1, n - 1)(rng);
        ull x = uniform_int_distribution<ull>(0, n - 1)(rng);
        ull y = x;
        ull d = 1;

        while (d == 1) {
            x = (mul_mod(x, x, n) + c) % n;
            y = (mul_mod(y, y, n) + c) % n;
            y = (mul_mod(y, y, n) + c) % n;
            ull diff = x > y ? x - y : y - x;
            d = gcd(diff, n);
        }

        if (d != n) {
            return d;
        }
    }
}

void factorize(ull n, vector<ull> &fac) {
    if (n == 1) {
        return;
    }
    if (miller_rabin(n)) {
        fac.push_back(n);
        return;
    }

    ull d = pollard_rho(n);
    factorize(d, fac);
    factorize(n / d, fac);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            cin >> a[i][j];
        }
    }
    cin >> target_x >> target_y;

    ull start = a[target_x][target_y];
    if (start == 1) {
        cout << 0 << '\n';
        return 0;
    }

    vector<ull> fac;
    factorize(start, fac);
    sort(fac.begin(), fac.end());
    fac.erase(unique(fac.begin(), fac.end()), fac.end());

    int ans = 0;
    for (int idx = 0; idx < (int) fac.size(); idx++) {
        ull p = fac[idx];
        int best = INT_MAX;

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                if (a[i][j] % p != 0) {
                    int d = abs(i - target_x) + abs(j - target_y);
                    if (d < best) {
                        best = d;
                    }
                }
            }
        }

        if (best == INT_MAX) {
            cout << -1 << '\n';
            return 0;
        }
        ans = max(ans, best);
    }

    cout << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(k · n · m)$
空间复杂度： $O(nm)$

其中 k 是目标点初始值的不同质因子个数，实际非常小。

总结

这题最关键的不是 gcd 本身，而是把局部更新看成“曼哈顿半径不断扩大的菱形区域 gcd”。

一旦把这个传播范围看清楚，问题就从“动态模拟”变成了“每个质因子最早什么时候会被周围某个格子消掉”。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

P7243 最大公约数

题目背景

“寻求最大公约数是人民民主的真谛。……”

初秋，从枝丫滴下的阳光，柔和，在教室的窗棱溅起，润湿晨读的少女的脸颊。

“阿绫，阿绫”，天依低俯身子，八字辫耷拉在竖起的课本沿，“我们的最大公约数是多少呢？”

“一定不小吧”，左手悄悄捏捏天依的小臂，“比如呀，有一个公因子，叫做‘你喜欢我，我也喜欢你’。”

题目描述

相反，人际圈形形色色，公约数小得可怜，似乎很难保持自己的个性因而变成无趣的人呢。

现在把人际抽象成一个 $n \times m$ 的矩形，每个人初始的个性为 $a_{i,j}$ 。从第二天开始，每个人会与上下左右四个人（如果存在）建立人际关系，其个性变为昨天自己和四周人个性的最大公约数。那么对于第 $x$ 行第 $y$ 列的人，在多少天后他的个性会变为 $1$ 呢？

简化题意

有一个 $n \times m$ 的矩阵 $a$ 。对一个矩阵进行变换，定义为将这个矩阵内的所有元素变为其上下左右四个元素（不存在则忽略）及自身的最大公约数。询问 $a_{x,y}$ 在进行最少多少次变换之后会变成 $1$ 。如果可以使 $a_{x,y}$ 经过若干次变换变成 $1$ ，输出其中最小的次数；否则输出 $-1$ 。

输入格式

第一行两个整数 $n,m$ ，表示矩阵的行数和列数。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 列的整数 $a_{i,j}$ 描述了该位置的人的初始个性。

接下来一行两个整数 $x,y$ ，表示某个指定的人的位置。

输出格式

一行一个整数 $d$ ，表示第 $x$ 行第 $y$ 列的人的个性会在 $d$ 天后变为 $1$ ；特别地，若永远不会变为 $1$ ，应输出 $-1$ 。

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

1-1

输入输出样例 #3

输入 #3

text

输出 #3

text

说明/提示

样例解释 3

第一天的个性矩阵（也就是最开始的矩阵）为

\begin{pmatrix} 3&2&3\\ 2&3&2\\ 3&2&3 \end{pmatrix}

第二天的个性矩阵为

\begin{pmatrix} 1&1&1\\ 1&1&1\\ 1&1&1 \end{pmatrix}

可见只需要经过一天，

a_{2,2}

就会变为

1

，所以答案为

1

。

数据规模与约定

本题采用捆绑测试。

对于 $100\%$ 的数据， $1\le n,m\le 2\times 10^3$ ， $1\le a_{i,j}\le 10^{18}$ ， $1\le x\le n$ ， $1\le y\le m$ 。

子任务	分值	$n,m$	特殊限制
1	1	/	保证给出的位置个性永远不会变为 $1$
2	1	/	保证 $a_{x,y}=1$
3	3	$ \le 2$	/
4	10	$ \le 10^2$	/
5	30	$ \le 5\times 10^2$	/
6	10	/	保证对于所有的 $a_{i,j} \le 2$
7	10	/	保证 $x$ 与 $y$ 都等于 $1$
8	35	/	/

最大公约数

目录

题意

思路

第 t 天对应一个曼哈顿菱形

只需要关心目标值的质因子

为什么要用 Pollard Rho

代码

复杂度

总结

一图流解析