## 1. Abridged problem statement

Given a grid with N rows and M columns, Petya stands at the bottom-left cell. Every other cell contains an enemy. A single shot from Petya's position kills all enemies lying on the same straight line. Compute the minimum number of shots needed to eliminate all enemies.

---

## 2. Detailed editorial

### Problem restatement and reduction

- Label Petya's cell as (1,1). Every other cell has coordinates (i,j) with 1≤i≤N, 1≤j≤M, and (i,j)≠(1,1).
- A shot in direction (Δi,Δj) destroys every enemy whose offset from Petya is an integer multiple of (Δi,Δj).
- Thus distinct shots correspond one-to-one with primitive direction vectors (dx,dy) where dx=i−1, dy=j−1, not both zero, and gcd(dx,dy)=1.

We need to count how many integer pairs (dx,dy) satisfy:
0≤dx≤N−1, 0≤dy≤M−1, (dx,dy)≠(0,0), gcd(dx,dy)=1.

### Breakdown

**A. Horizontal and vertical shots**
- dx=0, dy>0 → only dy=1 is primitive ⇒ one vertical shot (if M>1).
- dy=0, dx>0 → only dx=1 is primitive ⇒ one horizontal shot (if N>1).

**B. Shots at non-axis directions**
- Count pairs with dx≥1 and dy≥1, gcd(dx,dy)=1.
- Total such pairs = ∑_{dx=1..N−1} ∑_{dy=1..M−1} [gcd(dx,dy)=1].

Directly iterating over dx,dy up to 10^6×10^6 is impossible. Use a divisor-based sieve (inclusion–exclusion via Möbius inversion) to count the number of coprime pairs efficiently:

Let A = N−1, B = M−1.
Let f(d) = number of pairs (dx,dy) with dx≥1, dy≥1, gcd(dx,dy)=d.
- f(d) = floor(A/d) * floor(B/d).

We want g = f(1), but f(1) counts all pairs including higher-gcd ones. By standard Möbius-style inversion (or by subtracting multiples), we compute for d from min(A,B) down to 2:
1. dp[d] = f(d) − ∑_{k≥2} dp[k·d].
2. g = dp[1].

The code starts with `ans = (N-1)*(M-1)` (total interior pairs) and subtracts dp[d] for d≥2 as it computes them, leaving only the coprime count.

**Final answer** = g + (N>1 ? 1 : 0) + (M>1 ? 1 : 0).

### Complexity

O(min(N,M) · log(min(N,M))) by iterating divisors, which is fine up to 10^6.

---

## 3. C++ Solution

```cpp
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int n, m;

void read() { cin >> n >> m; }

void solve() {
    // The minimum number of shots equals the number of distinct directions
    // from Petya's corner to the other cells, i.e. the number of visible
    // lattice points in the (N-1) x (M-1) interior block plus the two axis
    // directions (the rest of the bottom row and the left column).
    //
    // A point (a, b) with 1 <= a <= N-1, 1 <= b <= M-1 is visible exactly when
    // gcd(a, b) = 1. Count coprime pairs by inclusion-exclusion over the gcd d:
    // dp[d] = (number of pairs whose gcd is exactly d) is ((N-1)/d)*((M-1)/d)
    // minus dp of all multiples of d. Visible interior pairs is dp[1], computed
    // as total pairs minus dp[d] for d >= 2. Finally add the two axis shots
    // when the corresponding side has more than one cell.

    int64_t ans = (n - 1) * 1ll * (m - 1);
    vector<int64_t> dp(min(n, m) + 1, 0);
    for(int d = min(n, m); d >= 2; d--) {
        dp[d] = ((n - 1) / d) * 1ll * ((m - 1) / d);
        for(int d2 = 2 * d; d2 <= min(n, m); d2 += d) {
            dp[d] -= dp[d2];
        }

        ans -= dp[d];
    }
    cout << ans + (n > 1) + (m > 1) << '\n';
}

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

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}
```

---

## 4. Python Solution

```python
import sys
import threading

def main():
    data = sys.stdin.read().split()
    n, m = map(int, data)
    # A = n-1, B = m-1
    A, B = n - 1, m - 1

    # Count all pairs dx>=1, dy>=1 unconstrained by gcd
    total_pairs = A * B

    # We will build dp[d] = number of pairs (dx,dy) with gcd(dx,dy)==d
    # for d from 1..lim, but we only need d>=2 to subtract non-coprime.
    lim = min(A, B)
    dp = [0] * (lim + 1)

    # Inclusion–exclusion from largest d down to 2
    for d in range(lim, 1, -1):
        # pairs where dx and dy share factor d
        cnt = (A // d) * (B // d)
        # subtract those already attributed to multiples of d
        multiple = 2 * d
        while multiple <= lim:
            cnt -= dp[multiple]
            multiple += d
        dp[d] = cnt
        total_pairs -= cnt  # remove all non-coprime pairs

    # total_pairs now equals count of dx>=1,dy>=1,gcd=1
    # plus horizontal shot if n>1 (dx>0,dy=0) and vertical if m>1
    shots = total_pairs
    if n > 1:
        shots += 1
    if m > 1:
        shots += 1

    print(shots)

if __name__ == "__main__":
    threading.Thread(target=main).start()
```

---

## 5. Compressed editorial

Count primitive direction vectors from (1,1) to every enemy cell. Axis directions give up to two shots. Non-axis directions correspond to all integer pairs (dx,dy) with 1≤dx≤N−1, 1≤dy≤M−1 and gcd(dx,dy)=1. Use a divisor sieve: for each d from min(N−1,M−1) down to 2 compute dp[d]=⌊(N−1)/d⌋·⌊(M−1)/d⌋−∑_{k≥2}dp[kd]. Subtract these non-coprime counts from total (N−1)(M−1) to get coprime pairs. Add the two axis shots if applicable. Total complexity O(min(N,M)·log min(N,M)).
