Cerința

Îl cunoașteți, cred, pe Cătălin, fan-ul numărul 1 al greșelilor. Ei bine, în teza la mate, Cătălin a făcut N greșeli. Presupunând, prin reducere la absurd, că el corectează o greșeală i, poate alege să corecteze o singură greșeală j, cu proprietatea 1<j<i şi i%j=0. El știe că, dacă face această alegere poate să continue din greșeala j, după aceeași regulă și nu mai poate reveni la o greșeala anterioară.

Cătălin alege T greșeli G[1] G[2] … G[T] și dorește să știe, pentru fiecare G[i], numărul maxim de greșeli pe care le poate corecta dacă începe rezolvând-o pe aceasta.

Date de intrare

Fișierul de intrare greselile.in conține pe prima linie două numere N și T unde N este numărul de greșeli și T numărul de întrebări. Următoarele T linii conțin câte un număr natural nenul reprezentând greșeala de la care Cătălin vrea să pornească corectarea.

Date de ieșire

Fișierul de ieșire greselile.out va conține fiecare linie i un singur număr natural reprezentând numărul maxim de greșeli care pot fi corectate dacă ar începe Cătălin cu greșeala G[i].

Restricții și precizări

1 ≤ N, T ≤ 1.000.000

Exemplu

greselile.in

greselile.out

Explicație

Corectează doar 3 deoarece numărul nu are divizori proprii.
Pornind cu 4 el va corecta 4 şi 2.
Pornind cu 6 el va corecta 6 şi 3 sau 6 și 2, maximul fiind de 2 greşeli corectate.
ș.a.m.d.

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 Catalin si greselile:

// sursa 100p Turcuman Vlad

#include <fstream>
#include <iostream>

#define NMax 1000000
using namespace std;
ifstream fin("greselile.in");
ofstream fout("greselile.out");

int n,k,t,g;
int ans[NMax+2];

int main()
{
    fin>>n;

    for(int g = 2; g<=n+1; g++)
    {
        ans[g] ++;
            for(int it = g * 2; it <=n+1; it += g)
                ans[it] = max(ans[it],ans[g]);
    }

   fin>>t;

    while(t--)
    {
        fin>>g;
        fout<<ans[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 #1916 Catalin si greselile

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1916 Catalin si greselile 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 #1916 Catalin si greselile