Soluție HackerRank pentru Satisfactory Pairs, subdomeniul Number Theory, în C++14. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Satisfactory Pairs
  • Domeniu: Number Theory
  • Limbaj: C++14

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

Cerință

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 · a + y · 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 ≤ n ≤ 3 × 10^5

Cod sursă

#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;
}
HackerRank Number Theory – Satisfactory Pairs