<|instruction|>
Solve the below problem. The solution should start with an abridged problem statement. Then key observations. Then full solution based on the observations. Then C++ and Python implementations with comments.

370. Rifleman
Time limit per test: 0.75 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



Petya is a rifleman. He is located in the leftmost bottom cell of the rectangular field Nx M, all other cells of the field are occupied by enemies. Petya and his enemies are points and they are located in the centers of the corresponding cells. Petya has a power supersecret weapon Ber-9875 which destroys all enemies along a straight line. Your task is to calculate the minimum number of shots to do this.

Input
The first line of the input contains two integers N and M (1≤ N, M≤ 106).

Output
Output file must contain the minimum number of shots.

Example(s)
sample input
sample output
3 4
7

sample input
sample output
2 10
11

<|response|>
## 1. Abridged problem statement

Petya stands at the bottom-left cell (1,1) of an N×M grid. Every other cell contains one enemy at its center. A single shot from Petya's position destroys all enemies lying exactly on some straight line through (1,1). Compute the minimum number of shots required to eliminate all enemies.

---

## 2. Key observations

- Any shot direction is determined by a vector (dx, dy) from (1,1) to an enemy cell (i,j), where dx=i−1, dy=j−1, not both zero.
- A shot in direction (dx, dy) also destroys all enemies at (1+k·dx, 1+k·dy), k≥1 integer, so we only need one shot per primitive (dx, dy) with gcd(dx, dy)=1.
- Axis directions: horizontal (dx>0, dy=0) is primitive only for dx=1 ⇒ at most one horizontal shot if N>1. Vertical (dx=0, dy>0) is primitive only for dy=1 ⇒ at most one vertical shot if M>1.
- Non-axis directions correspond to all integer pairs 1≤dx≤N−1, 1≤dy≤M−1 with gcd(dx, dy)=1. Counting these directly in O(NM) is impossible when N,M≤10^6.

---

## 3. Full solution approach

Let A=N−1, B=M−1. We want: count = #{1≤dx≤A, 1≤dy≤B : gcd(dx,dy)=1}. Then answer = count + (N>1 ? 1 : 0) + (M>1 ? 1 : 0).

To compute count efficiently, use the classic divisor-sieve / Möbius-inversion idea, but instead of building dp[1] explicitly we subtract the non-coprime pairs from the total:

Start with total = A·B = the number of all interior pairs (dx,dy). For each d from min(N,M) down to 2, define dp[d] = number of pairs whose gcd is exactly d: dp[d] = ⌊A/d⌋·⌊B/d⌋ − ∑_{k≥2, k·d≤min(N,M)} dp[k·d]. Every dp[d] with d≥2 is a non-coprime block, so subtract it from total. After the loop, total equals exactly the number of coprime pairs. Each subtraction over a divisor d costs O(lim/d), so the whole sieve runs in O(lim·log lim).

---

## 4. 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;
}
```

---

## 5. 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()
```
