HackerRank Number Theory – Satisfactory Pairs

Challenge: Satisfactory Pairs

Subdomeniu: Number Theory (number-theory)

Scor cont: 60.0 / 60

Submission status: Accepted

Submission score: 1.0

Submission ID: 464757124

Limbaj: cpp14

Link challenge: https://www.hackerrank.com/challenges/pairs-again/problem

Cerinta

Given a positive integer, $n$, find and print the number of pairs of positive integers $(a, b)$, where $a < b$, that exist such that the equation $x \cdot a + y \cdot b = n$ (where $x$ and $y$ are positive integers) has at least one solution.

Input Format

A single positive integer denoting $n$.

Output Format

Print a single integer denoting the number of such pairs.

Constraints

* $4 \leq n \leq 3 \times 10^5$

Cod sursa

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

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

    int n;
    cin >> n;

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

    vector<int> seen(n + 1, 0);
    int stamp = 0;

    long long ans = 0;

    for (int a = 1; a < n; ++a) {
        ++stamp;
        int maxX = (n - 1) / a;
        for (int x = 1; x <= maxX; ++x) {
            int r = n - a * x;
            // Choose b | r, and y = r / b >= 1.
            for (int b : divisors[r]) {
                if (b > a && seen[b] != stamp) {
                    seen[b] = stamp;
                    ++ans;
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}