k-perechi de numere consecutive

Numărarea divizorilor

Divizorii unui număr natural n se grupează în perechi: dacă d îl divide pe n, atunci și n/d îl divide. Cei doi divizori dintr-o pereche se află de o parte și de alta a rădăcinii pătrate a lui n, așa că este de ajuns să se caute divizorii d cu proprietatea d² ≤ n, iar pentru fiecare dintre ei să se numere și perechea lui.

Singurul caz în care perechea nu aduce un divizor nou este cel în care d = n/d, adică n este pătrat perfect și d este rădăcina lui. Atunci divizorul se numără o singură dată.

Pentru n = 27, divizorii găsiți în această ordine sunt 1 și 27, apoi 3 și 9, deci în total 4. Pentru n = 36, care este pătrat perfect, se găsesc 1 și 36, 2 și 18, 3 și 12, 4 și 9, apoi 6, care se numără o singură dată, deci în total 9 divizori.

Descrierea algoritmului în limbaj natural

Se deschide fișierul și se citesc cele trei numere: k, x și y. Enunțul spune că intervalul este delimitat de x și y, fără să precizeze care dintre ele este capătul din stânga: exemplul dat conține atât valorile 80 și 22, cât și valorile 22 și 70. De aceea, dacă x este mai mare decât y, cele două valori se interschimbă, astfel încât intervalul să fie [x, y], cu x ≤ y.

Se parcurg apoi numerele din interval, de la x la y−1, iar pentru fiecare număr i se verifică dacă i și i+1 formează o k-pereche, adică dacă amândouă au exact k divizori. Ambele numere trebuie să se afle în interval, condiție îndeplinită prin faptul că parcurgerea se oprește la y−1.

Numărul de divizori al unui număr nu se calculează de două ori. Înainte de parcurgere se determină numărul de divizori al lui x, iar la fiecare pas se calculează numai numărul de divizori al lui i+1; valoarea determinată la pasul curent devine, la pasul următor, numărul de divizori al primului element din pereche.

Se numără perechile care îndeplinesc condiția și, la sfârșit, se afișează pe ecran valoarea obținută.

Programul

#include <iostream>
#include <fstream>
using namespace std;

/* Intoarce numarul divizorilor lui n. Divizorii se cauta pana la radacina
   patrata a lui n; pentru fiecare divizor d gasit se numara si perechea
   lui, n/d, in afara cazului in care cei doi coincid (n patrat perfect). */
int nrDiv(int n) {
    int nr = 0;
    for (int d = 1; d * d <= n; d++)
        if (n % d == 0) {
            nr++;
            if (d != n / d)
                nr++;
        }
    return nr;
}

int main() {
    ifstream f("def2024.in");
    int k, x, y;

    f >> k >> x >> y;
    f.close();

    /* Capetele pot fi date in orice ordine. */
    if (x > y) {
        int aux = x;
        x = y;
        y = aux;
    }

    int cate = 0;
    int divPrimul = nrDiv(x);

    for (int i = x; i < y; i++) {
        int divAlDoilea = nrDiv(i + 1);
        if (divPrimul == k && divAlDoilea == k)
            cate++;
        divPrimul = divAlDoilea;
    }

    cout << cate;

    return 0;
}