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

491. Game for Little Johnny
Time limit per test: 0.75 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Most of all in his life John likes his little son Johnny and his favorite integer number N. Well, actually John also likes math, so he wants his son to learn math from the early childhood.

To achieve this goal John plays the following game with Johnny. Each morning he tells the following tale to the son:

"In some magic kingdom there is a very tasty sweet cake and this cake costs exactly N bananas (a monetary unit of this kingdom). However, there are only two types of banknotes in this kingdom, one with the value of A bananas and the other with the value of B bananas (A < B).

According to the kingdom's laws, when buying a product, one has to use the set of banknotes with the total value equal to the product's cost so that no change is required and this set must contain at least one banknote of each of two types. Unfortunately, people in the kingdom are very bad at math, so nobody can find a way to buy the cake. Would you be able to buy it, Johnny?"

In other words, Johnny is given three integers N, A and B, 1 ≤ A < B ≤ N, and is required to find integers x, y ≥ 1 such that A· x + B· y = N. If Johnny succeeds at this task, John gives him a real tasty sweet cake as a prize.

For each next day John is going to use different numbers A and B in his tale, but the number N will always be the same (it's his favorite integer after all!). John likes his son, so he wants to always choose A and B in such way that Johnny's task has a solution. And of course John doesn't want to use the same pair (A, B) for two or more different days.

John is worried about the following question: for how long is he able to tell this tale, that is, how many different pairs (A, B) exist such that Johnny's task has a solution? However, John is not so good at math himself (it's a secret, don't tell it to Johnny!), so you have to help him to answer this question.

Input
The input file contains one integer N ().

Output
The output file must contain one integer, the amount of different pairs (A, B) such that Johnny's task has a solution.

Example(s)
sample input
sample output
10
15

Note. The pairs from the example test case are (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (2, 3), (2, 4), (2, 6), (2, 8), (3, 4), (3, 7), (4, 6).

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

Given an integer **N**, count how many distinct pairs **(A, B)** exist such that:

- \(1 \le A < B \le N\)
- there exist integers \(x \ge 1\) and \(y \ge 1\) satisfying  
  \[
  A x + B y = N
  \]

Output the number of such pairs \((A,B)\).

---

## 2) Key observations needed to solve the problem

1. **Fixing \(A\) and \(x\) determines the remaining sum.**  
   From
   \[
   Ax + By = N
   \]
   we get
   \[
   By = N - Ax
   \]
   Let \(R = N - Ax\). We need \(R > 0\), so \(Ax < N\).

2. **For a given remainder \(R\), valid \(B\) are exactly the divisors of \(R\).**  
   If \(B \mid R\), then \(y = R/B\) is an integer and since \(R>0\), automatically \(y \ge 1\).

3. **We must enforce \(A < B\)** (problem constraint), so when iterating divisors \(B\) of \(R\), count only those with \(B > A\).

4. **Avoid double counting for the same \(A\).**  
   The same \(B\) might appear for multiple values of \(x\). For each fixed \(A\), count each \(B\) only once using a `visited[B]` marker array:
   - `visited[B] == A` means we already counted pair \((A,B)\).

5. **Precomputing divisors for all numbers up to \(N\)** enables fast enumeration:
   - Build `divisors[m]` for all \(m \le N\) using a sieve-like loop in \(O(N \log N)\).

---

## 3) Full solution approach

1. **Read \(N\).**
2. **Precompute divisors for every number \(1..N\):**
   - For each \(d\) from 1 to \(N\), add \(d\) to all `divisors[m]` where \(m\) is a multiple of \(d\).
3. Initialize:
   - `visited[1..N] = 0`
   - `answer = 0`
4. For each \(A\) from 1 to \(N-1\):
   - For \(x = 1\) while \(A \cdot x < N\):
     - \(R = N - A\cdot x\)
     - For each divisor \(B\) in `divisors[R]`:
       - If \(B > A\) and `visited[B] != A`, then count it:
         - `visited[B] = A`
         - `answer++`
5. Print `answer`.

**Complexity (practical):**
- Divisor sieve: \(O(N \log N)\)
- Iterating \(A\) and \(x\): \(\sum_{A=1}^{N-1} O(N/A) = O(N \log N)\)
- Total fits typical constraints for this problem with efficient implementation.

---

## 4) C++ implementation with detailed comments

```cpp
#include <bits/stdc++.h>
using namespace std;

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

    int N;
    cin >> N;

    // divisors[m] will store all positive divisors of m
    vector<vector<int>> divisors(N + 1);

    // Precompute divisors for every number 1..N in sieve style:
    // For each d, add d to all multiples of d.
    for (int d = 1; d <= N; d++) {
        for (int m = d; m <= N; m += d) {
            divisors[m].push_back(d);
        }
    }

    // visited[B] is used to avoid double counting pairs (A,B) for a fixed A.
    // Trick: instead of clearing visited for each A, store marker = A.
    vector<int> visited(N + 1, 0);

    long long ans = 0;

    // Enumerate all A
    for (int A = 1; A < N; A++) {

        // Enumerate all x >= 1 such that A*x < N (so remainder is positive)
        for (int x = 1; 1LL * A * x < N; x++) {
            int R = N - A * x;      // must equal B*y

            // All valid B are divisors of R
            for (int B : divisors[R]) {
                // Need A < B and count each B only once for this A
                if (B > A && visited[B] != A) {
                    visited[B] = A;
                    ans++;
                }
            }
        }
    }

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

---

## 5) Python implementation with detailed comments

```python
import sys

def solve() -> None:
    N = int(sys.stdin.readline().strip())

    # divisors[m] will store all positive divisors of m
    divisors = [[] for _ in range(N + 1)]

    # Sieve-like divisor precomputation:
    # For each d, append d to all multiples of d.
    for d in range(1, N + 1):
        for m in range(d, N + 1, d):
            divisors[m].append(d)

    # visited[B] = A means for this fixed A we already counted pair (A, B).
    visited = [0] * (N + 1)

    ans = 0

    # Enumerate all A
    for A in range(1, N):
        x = 1
        while A * x < N:
            R = N - A * x  # we need B*y = R

            for B in divisors[R]:
                if B > A and visited[B] != A:
                    visited[B] = A
                    ans += 1

            x += 1

    print(ans)

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

