Grade 12 · Baccalaureate exam reviewCitește în română

Subprogram: how many numbers in a range have an odd number of divisors

Original: Subprogram — câte numere dintr-un interval au un număr impar de divizori

O(1)C++1759 lines4 examples

The idea

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.

Original description (Romanian)

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.

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

Examples

Example 1

Input

1 100

Expected output

10
Example 2

Input

10 50

Expected output

4
Example 3

Input

26 35

Expected output

0
Example 4

Input

1 1000000000000

Expected output

1000000

The code

Comments are in Romanian, as in the original collection. Edit freely: you can reset at any time.

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

Runs on a real g++ (C++17, -O2) through Compiler Explorer. Keep runs short; there's a time limit.