p491.in1
======================
10

=================
p491.ans1
======================
15

=================
p491.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;
}

=================
statement.txt
======================
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).

=================
