题意

在 $n \times n$ 网格上从 $(1,1)$ 走到 $(n,n)$，每次只能向右或向下。
格子 $(i,j)$ 的代价为 $\gcd(i,a) + \gcd(j,b)$。求最小总代价。

---

解法

代价可分离为行贡献和列贡献。
最优路径结构：存在转折点 $(x,y)$，使得：

• $x$ 是 $\le n$ 中与 $a$ 互质的最大整数
• $y$ 是 $\le n$ 中与 $b$ 互质的最大整数

路径分为两段： $1$. $(1,1) \to (x,y)$ $2$. $(x,y) \to (n,n)$

---

第一段代价

必须经过第 $1$ 行到第 $x$ 行、第 $1$ 列到第 $y$ 列，每行每列至少一次。
最小代价为：

$$\text{cost}_1 = \sum_{i=1}^x \gcd(i,a) + \sum_{j=1}^y \gcd(j,b) - 2 $$

减 $2$ 是因为起点 $(1,1)$ 被重复计算（$\gcd(1,a)+\gcd(1,b)=1+1=2$）。

---

第二段代价

从 $(x,y)$ 到 $(n,n)$，网格大小为 $(n-x+1) \times (n-y+1)$，且 $n-x$ 和 $n-y$ 很小（通常 $< 50$）。
用动态规划：

• $dp[i][j]$：从 $(x,y)$ 到 $(x+i, y+j)$ 的最小代价
• 初始 $dp[0][0] = \text{cost}_1$
• 转移：$$dp[i][j] = \min(dp[i-1][j], dp[i][j-1]) + \gcd(x+i, a) + \gcd(y+j, b) $$
• 答案 $= dp[n-x][n-y]$

如果 $x=n$ 且 $y=n$，直接输出 $\text{cost}_1$。

---

复杂度

• 找 $x,y$：$O(n)$ 但实际很小
• DP 网格大小 $\le 50 \times 50$，常数时间
• 总复杂度 $O(n)$

---

代码

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
    while (b) {
        a %= b;
        swap(a, b);
    }
    return a;
}

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

    ll n, a, b;
    cin >> n >> a >> b;

    ll x = n, y = n;
    while (x >= 1 && gcd(x, a) != 1) x--;
    while (y >= 1 && gcd(y, b) != 1) y--;

    ll ans = 0;
    for (ll i = 1; i <= x; i++) ans += gcd(i, a);
    for (ll j = 1; j <= y; j++) ans += gcd(j, b);
    ans -= 2;

    if (x == n && y == n) {
        cout << ans << "\n";
        return 0;
    }

    vector<vector<ll>> dp(n - x + 2, vector<ll>(n - y + 2, 1e18));
    dp[0][0] = ans;

    for (ll i = 0; i <= n - x; i++) {
        for (ll j = 0; j <= n - y; j++) {
            if (i == 0 && j == 0) continue;
            ll cur_i = x + i;
            ll cur_j = y + j;
            ll from_left = (j > 0) ? dp[i][j-1] : 1e18;
            ll from_up = (i > 0) ? dp[i-1][j] : 1e18;
            dp[i][j] = min(from_left, from_up) + gcd(cur_i, a) + gcd(cur_j, b);
        }
    }

    cout << dp[n - x][n - y] << "\n";

    return 0;
}