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

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;

void read() { cin >> n; }

void solve() {
    // We can iterate through all values A, and try to figure out what the valid
    // values B are. Let's fix all O(N) values A. We want A*x+B*y=n. The first
    // observation is that there are only O(N/A) values for X, which means
    // overall fixing (A, x) is O(N log N) due to the sum of the harmonic
    // sequence. Afterwards, we can try to find all valid (B, y) such that
    // B*y=n-A*x. This is precisely the factors of n-A*x which in practice is
    // O(N^(1/3)), but we should precompute it in a sieve like way too.
    //
    // One thing we should be careful about is that for some A we shouldn't over
    // count the values B. We can do this directly with a global visited array,
    // where one neat way is to just use an integer marker based on A. This
    // O(N^(4/3) log N) which should be fast enough.

    vector<vector<int>> divisors(n + 1);
    for(int d = 1; d <= n; d++) {
        for(int m = d; m <= n; m += d) {
            divisors[m].push_back(d);
        }
    }

    vector<int> visited(n + 1, 0);
    int ans = 0;

    for(int a = 1; a < n; a++) {
        for(int x = 1; a * x < n; x++) {
            int remainder = n - a * x;
            for(int b: divisors[remainder]) {
                if(b > a && visited[b] != a) {
                    visited[b] = a;
                    ans++;
                }
            }
        }
    }

    cout << ans << '\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 implementation with detailed comments

```python
import sys

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

    # Precompute divisors for every number 1..n using a sieve-like method.
    # divisors[m] = list of all d such that d divides m.
    divisors = [[] for _ in range(n + 1)]
    for d in range(1, n + 1):
        for m in range(d, n + 1, d):
            divisors[m].append(d)

    # visited[b] stores the last 'a' for which we already counted pair (a,b).
    # This avoids clearing a boolean array for every a.
    visited = [0] * (n + 1)

    ans = 0

    # Enumerate all a from 1..n-1
    for a in range(1, n):
        # Enumerate x>=1 while a*x < n so remainder stays positive
        x = 1
        while a * x < n:
            remainder = n - a * x  # this must equal b*y

            for b in divisors[remainder]:
                if b > a and visited[b] != a:
                    visited[b] = a
                    ans += 1

            x += 1

    print(ans)

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