<|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:

a. Let lim = min(A, B).  
b. For each d from lim down to 1, define  
   f(d) = ⌊A/d⌋·⌊B/d⌋ = number of pairs (dx,dy) both divisible by d.  
c. We want dp[d] = number of pairs with gcd(dx,dy)=d. Then by inclusion–exclusion:  
   dp[d] = f(d) − ∑_{k≥2, k·d≤lim} dp[k·d].  
d. In particular, the number of coprime pairs is dp[1].  
e. We can accumulate dp[d] from d=lim down to 1 in O(lim·(1 + 1/2 + 1/3 + …)) = O(lim·log lim).  
f. Finally, answer = dp[1] + (N>1) + (M>1).

4. C++ implementation with detailed comments  
```cpp
#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    long long N, M;
    cin >> N >> M;
    // A = max dx, B = max dy
    long long A = N - 1;
    long long B = M - 1;
    // lim = smallest of A and B
    int lim = int(min(A, B));

    // dp[d] will hold number of pairs (dx,dy) with gcd(dx,dy)==d
    vector<long long> dp(lim + 1, 0);

    // Precompute f(d) = floor(A/d) * floor(B/d) on the fly,
    // then subtract contributions of multiples to get dp[d].
    for (int d = lim; d >= 1; --d) {
        // total pairs where both dx,dy are multiples of d
        long long f = (A / d) * (B / d);
        // subtract those already counted for multiples of d
        for (int kd = 2*d; kd <= lim; kd += d) {
            f -= dp[kd];
        }
        dp[d] = f;
    }

    // dp[1] is the count of coprime pairs with dx>=1,dy>=1
    long long shots = dp[1];
    // add one horizontal shot if dx>0,dy=0 is needed (i.e. N>1)
    if (N > 1) shots += 1;
    // add one vertical shot if dx=0,dy>0 is needed (i.e. M>1)
    if (M > 1) shots += 1;

    cout << shots << "\n";
    return 0;
}
```

5. Python implementation with detailed comments  
```python
import sys

def main():
    data = sys.stdin.read().split()
    N, M = map(int, data)
    A, B = N - 1, M - 1
    lim = min(A, B)

    # dp[d] = number of pairs (dx,dy) with 1≤dx≤A,1≤dy≤B and gcd(dx,dy)==d
    dp = [0] * (lim + 1)

    # Build dp from largest d down to 1
    for d in range(lim, 0, -1):
        # f = count of pairs where both dx,dy divisible by d
        f = (A // d) * (B // d)
        # subtract counts for multiples of d
        multiple = 2 * d
        while multiple <= lim:
            f -= dp[multiple]
            multiple += d
        dp[d] = f

    # dp[1] is number of coprime (dx,dy) pairs with dx>=1,dy>=1
    shots = dp[1]
    # add horizontal shot if N>1, vertical if M>1
    if N > 1:
        shots += 1
    if M > 1:
        shots += 1

    print(shots)

if __name__ == "__main__":
    main()
```

Explanation summary:  
- We count all directions (dx,dy) with gcd=1 using a sieve over divisors.  
- We add two special cases for purely horizontal and vertical shots.  
- Total time is O(min(N,M)·log min(N,M)), which is efficient for N,M up to 10^6.