Rezolvare completă PbInfo #2174 numar6

Presupunem că avem n numere prime notate a1, a2, ..., an sortate strict crescător. Formăm un șir strict crescător b ale cărui elemente sunt toţi multiplii acestor n numere prime astfel încât, multipli comuni apar o singură dată. Presupunem că numerotarea pozițiilor elementelor din șirul b începe tot cu 1.

Cerința

Scrieți un program care citește din fişierul de intrare valoarea lui n şi apoi cele n elemente ale şirului a, determină elementul de pe poziţia m din şirul b şi afişează în fişierul de ieşire valoarea acestuia.

Date de intrare

Fișierul de intrare numar6.in conține pe prima linie două numere naturale separate printr-un spațiu care reprezintă primul valoarea lui n și al doilea valoarea lui m. Pe a doua linie n numere naturale prime separate prin câte un spațiu care reprezintă valorile elementelor șirului a. Aceste valori sunt dispuse în ordine strict crescătoare iar ultima dintre ele este mai mică decât un milion.

Date de ieșire

Fișierul de ieșire numar6.out va conţine pe prima linie o singură valoare care reprezintă termenul de pe poziţia m din şirul b.

Restricții și precizări

  • Pentru 30% din teste n ≤ 20, m ≤ 1000, a1 ≤ 50
  • Pentru celelalte 70% din teste 21 ≤ n ≤ 100, 1001 ≤ m ≤ 15000, 51 ≤ a1 ≤ 1000
  • an < 1000000

Exemplul 1:

numar6.in

3 10 
2 3 5

numar6.out

14

Explicație

Şirul b e format din valorile: 2,3,4,5,6,8,9,10,12,14,15,16,18,20,21,22 …
Pe poziţia 10 se află numărul 14

Exemplul 2:

numar6.in

4 20
7 23 37 131

numar6.out

98

Exemplul 3:

numar6.in

3 11111
977 1009 1031

numar6.out

3726237

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 numar6:

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

int t[105], n, m;
bitset<nmax> a;

int main()
{
    int i, MAX, j, x;
    ifstream fin("numar6.in");
    ofstream fout("numar6.out");
    fin >> n >> m;
    for (i = 1; i <= n; ++i)
        fin >> t[i];
    MAX = m * t[1];
    for (i = 1; i <= n; ++i)
    {
        x = t[i];
        for (j = t[i]; j < MAX; j += x)
            a[j] = 1;
    }
    for (i = 1; i <= MAX && m > 0; i++)
        if (a[i] == 1)
            m--;
    fout << (i-1) << "\n";
    fin.close();
    fout.close();
    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 #2174 numar6

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2174 numar6 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!