思路：求a mod 上b后的值为amodb, 求gcd(b, amodb)即可
int gcd(int a,int b){return b ? gcd(b, a % b) : a;
}void solve(){string a;cin >> a;int b;cin >> b;int amodb = 0;for(auto c : a){amodb = (amodb * 10 + (c - '0')) % b;}cout << gcd(b, amodb);
}
思路：二分答案，然后，判断当前二分的值符不符合，如果可以走到(n,n)就缩小答案，否则扩大答案。
#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define endl '\n'
#define pq priority_queue
using namespace std;
typedef pair<int, int> pii;int n, a[550][550], st[550][550];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, -1, 1};bool check(int mid) {queue<pii> q;memset(st, 0, sizeof(st));if (a[1][1] > mid) return false;q.push({1, 1});st[1][1] = true;while (!q.empty()) {int x = q.front().first, y = q.front().second;q.pop();for (int i = 0; i < 4; i++) {int px = x + dx[i], py = y + dy[i];if (px < 1 || py < 1 || px > n || py > n)continue;if (st[px][py])continue;if (a[px][py] > mid)continue;q.push({px, py});st[px][py] = true;}}return st[n][n];
}void solve() {cin >> n;for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {cin >> a[i][j];}}int l = 0, r = 1e9 + 2;while (l + 1 != r) {int mid = l + r >> 1;if (check(mid))r = mid;elsel = mid;}cout << r << endl;
}signed main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}
