Clasa a XII-a · Recapitulare pentru bacalaureatRead in English

Subprogram — câte numere dintr-un interval au un număr impar de divizori în C++

În engleză: Subprogram: how many numbers in a range have an odd number of divisors

O(1)C++1759 de linii4 exemple

Ideea

Cerința (tip subiectul III.1): subprogramul impare are parametrii a și b (1 ≤ a ≤ b ≤ 10^12) și întoarce câte numere din [a, b] au un număr impar de divizori. Varianta directă numără divizorii fiecărui număr și ar face miliarde de operații. Observația care o face eficientă: divizorii lui x vin în perechi (d, x / d), cu excepția lui d = x / d, deci numărul lor e impar exact când x este pătrat perfect. Pătratele din [1, x] sunt 1^2, ..., r^2 cu r = partea întreagă din radical din x, deci răspunsul este r(b) - r(a - 1). Radicalul calculat cu sqrt se corectează cu două bucle scurte, ca să evităm erorile de rotunjire.

Descrierea în engleză

The task (exam part III.1 style): the subprogram impare has the parameters a and b (1 ≤ a ≤ b ≤ 10^12) and returns how many numbers in [a, b] have an odd number of divisors. The direct version counts the divisors of every number and would perform billions of operations. The observation that makes it efficient: the divisors of x come in pairs (d, x / d), except when d = x / d, so their number is odd exactly when x is a perfect square. The squares in [1, x] are 1^2, ..., r^2 with r = the integer part of the square root of x, so the answer is r(b) - r(a - 1). The root computed with sqrt is corrected with two short loops, to avoid rounding errors.

Complexitate
O(1)
Clasa
Clasa a XII-a (Grade 12)

Exemple

Exemplul 1

Intrare

1 100

Ieșire așteptată

10
Exemplul 2

Intrare

10 50

Ieșire așteptată

4
Exemplul 3

Intrare

26 35

Ieșire așteptată

0
Exemplul 4

Intrare

1 1000000000000

Ieșire așteptată

1000000

Codul C++

Codul complet, cu comentarii în română. Îl poți modifica liber și îl poți reseta oricând.

subprogram-divizori-impari-interval.cpp
/*
 * Titlu: Subprogram — câte numere dintr-un interval au un număr impar de divizori
 * Clasa: 12
 * Capitol: Recapitulare pentru bacalaureat
 * Descriere: Cerința (tip subiectul III.1): subprogramul impare are parametrii a și
 *            b (1 ≤ a ≤ b ≤ 10^12) și întoarce câte numere din [a, b] au un număr
 *            impar de divizori. Varianta directă numără divizorii fiecărui număr
 *            și ar face miliarde de operații. Observația care o face eficientă:
 *            divizorii lui x vin în perechi (d, x / d), cu excepția lui d = x / d,
 *            deci numărul lor e impar exact când x este pătrat perfect. Pătratele
 *            din [1, x] sunt 1^2, ..., r^2 cu r = partea întreagă din radical din
 *            x, deci răspunsul este r(b) - r(a - 1). Radicalul calculat cu sqrt se
 *            corectează cu două bucle scurte, ca să evităm erorile de rotunjire.
 * Complexitate: O(1)
 *
 * Exemplu
 * Intrare: 1 100
 * Ieșire: 10
 *
 * Exemplu
 * Intrare: 10 50
 * Ieșire: 4
 *
 * Exemplu
 * Intrare: 26 35
 * Ieșire: 0
 *
 * Exemplu
 * Intrare: 1 1000000000000
 * Ieșire: 1000000
 */
#include <cmath>
#include <iostream>
using namespace std;

// Cel mai mare r cu r * r <= x.
long long radical(long long x)
{
    long long r = (long long)sqrt((double)x);
    while (r * r > x)
        r--;
    while ((r + 1) * (r + 1) <= x)
        r++;
    return r;
}

long long impare(long long a, long long b)
{
    return radical(b) - radical(a - 1);
}

int main()
{
    long long a, b;
    cin >> a >> b;
    cout << impare(a, b) << '\n';
    return 0;
}

Rulează pe un g++ adevărat (C++17, -O2) prin Compiler Explorer. Programele trebuie să se termine repede: există o limită de timp.