Se consideră două șiruri D=(D1,D2,...,Dn) și E=(E1,E2,... ,En) ce reprezintă descompunerea în factori primi pentru un număr natural nenul X, după cum urmează: Di – factorul prim, Ei – puterea la care apare factorul prim Di în descompunerea numărului X (1≤i≤n), unde n reprezintă numărul factorilor primi.

Cerința

Să se determine:
1. numărul total de divizori naturali ai lui X
2. divizorii lui X care aparțin intervalului [A,B], unde A și B sunt două numere naturale date.

Date de intrare

Fișierul de ieșire descmult.out conține pe prima linie un număr natural C care reprezintă cerința ce trebuie rezolvată (C=1 sau C=2).
A doua linie conține, despărțite prin câte un spațiu, trei numere naturale n A B, cu semnificația din enunț.
Pe linie a treia se află n numere naturale, separate prin câte un spațiu, ce reprezintă factorii primi D1 D2 ... Dn din descompunerea lui X.
Pe linia a patra se află n numere naturale, separate prin câte un spațiu, ce reprezintă puterile la care apar acești factori E1 E2 ... En.

Date de ieșire

Pentru C=1 se va rezolva doar prima cerință. În acest caz, fișierul de ieșire descmult.out va conține pe prima linie un singur număr natural nenul ce reprezintă numărul total de divizori naturali ai lui X.
Pentru C=2 se va rezolva cea de-a doua cerință. În acest caz, fișierul de ieșire descmult.out va conține, separați prin câte un spațiu, divizorii lui X ce aparțin intervalului [A,B].

Restricții și precizări

2 ≤ n ≤ 20
1 ≤ A ≤ B ≤ 10⁷
2 ≤ Di < 1000 (numere prime distincte), 1≤i≤n
1 ≤ Ei ≤ 10, 1≤i≤n
Factorii primi D1, D2,...,Dn nu sunt obligatoriu în ordine crescătoare
Se garantează că numărul maxim de divizori naturali ai lui X ≤ 10 ¹⁹
Intervalul [A,B] conține cel puțin un divizor
Numărul maxim de divizori aflați în intervalul [A,B] este ≤ 10 ⁶
Ordinea de afișare a divizorilor nu este importantă
Pentru rezolvarea corectă a cerinței 1 se acordă 20 de puncte, iar pentru cea de-a doua cerință se acordă 80 de puncte.

Exemplul 1:

descmult.in

descmult.out

Exemplul 2:

descmult.in

descmult.out

30 44 50 40 33

Explicație

Pentru primul exemplu C=1.
X=31*23*52*111=6600 și are 48 de divizori: 1, 2, 3, 4, 5, 6, 8, 10, 11, 12, 15, 20, 22, 24, 25, 30, 33, 40, 44, 50, 55, 60, 66, 75, 88, 100, 110, 120, 132, 150, 165, 200, 220, 264, 275, 300, 330, 440, 550, 600, 660, 825, 1100, 1320, 1650, 2200, 3300, 6600.

Pentru cel de-al doilea exemplu C=2.
X=31*23*52*111=6600.
Divizorii ce aparțin intervalului [30,50] sunt: 30,33,40,44,50. Ordinea de afișare a divizorilor nu este importantă.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema descmult:

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

ifstream f("descmult.in");
ofstream g("descmult.out");

int n, a, b, c, nr, k;
int D[23], E[23];
int F[1000003];
unsigned long long nrd, p;

int main(){

    f >> c;
    f >> n >> a >> b;
    for(int i=1; i<=n; ++i)
        f >> D[i];
    for(int i=1; i<=n; ++i)
        f >> E[i];

    if (c == 1) {
        nrd = 1;
        for(int i=1; i<=n; ++i)
            nrd *= (E[i] + 1);
        g << nrd << '\n';

    } else {
        F[1] = k = 1;
        if (a == 1) g << "1 ";
        for(int i=1; i<=n; ++i){

            p = 1;
            int m = k;
            while(E[i]--) {

                p *= D[i];
                if (p > b) break;
                for(int j=1; j<=k; ++j) {
                    long long y = F[j] * p;

                    if (y <= b) {
                        if (y >= a) g << y << " ";
                        F[++m] = y;
                    }
                }
            }

            k = m;
        }

        g << '\n';
    }

    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2494 descmult

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2494 descmult de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2494 descmult