Arpsod adoră două lucruri: matematica și clătitele bunicii sale. Într-o zi, aceasta s-a apucat să prepare clătite. Arpsod mănâncă toate clătitele începând de la a N-a clătită preparată, până la a M-a clătită preparată (inclusiv N și M). Pentru că el vrea să mănânce clătite cu diferite umpluturi și-a făcut următoarea regulă:

“Dacă numărul de ordine al clătitei este prim atunci aceasta va fi cu ciocolată. Dacă numărul de ordine este pătrat perfect sau cub perfect aceasta va fi cu gem. Dacă suma divizorilor numărului este egală cu însuși numărul de ordine atunci aceasta va fi cu înghețată. (se iau în considerare toți divizorii în afară de numărul în sine, inclusiv 1).

În cazul în care o clătită îndeplinește simultan mai multe condiții, se respectă prioritatea sortimentelor: ciocolată > gem > înghețată.
Dacă niciuna dintre condițiile de mai sus nu este îndeplinită, pentru cele cu numărul de ordine par, clătita va fi cu zahar, iar pentru numărul de ordine impar, clătita va fi simplă.”

Cerința

Cunoscându-se N și M, numere naturale, să se determine câte clătite a mâncat Arpsod în total și numărul de clătite din fiecare tip.

Date de intrare

Fișierul clatite.in conține pe prima linie numerele N și M separate printr-un spațiu.

Date de ieșire

Fișierul clatite.out conține pe prima line numărul total de clătite mâncate de Arpsod iar pe a doua linie 5 numere naturale separate printr-un spațiu reprezentând numărul de clătite mâncate, din fiecare tip (ordinea: ciocolata, gem, înghețată, zahăr, simplă).

Restricții și precizări

1 ≤ N, M ≤ 300.000

Exemplu

clatite.in

3 11

clatite.out

9
4 3 1 1 0

Explicație

Arpsod a mâncat 9 clătite dintre care:
4 cu ciocolată ( 3, 5, 7, 11 )
3 cu gem ( 4, 8, 9 )
1 cu înghețată ( 6 )
1 cu zahăr ( 10 ).
0 simple

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

#include <fstream>
using namespace std;

ifstream fin ( "clatite.in" );
ofstream fout ( "clatite.out" );

#define ciocolata 0
#define gem 1
#define inghetata 2
#define zahar 3
#define simpla 4

int TipClatita[5];

int main(){

    int N, M;
    
    fin >> N >> M;

    for ( int i = N; i <= M; ++i ){
        int x = i, power, term, SumaDiv = 1, NrDiv = 1;
        bool PP = 1, CP = 1;

        for ( int j = 2; j * j <= x; ++j ){
            term = j;
            power = 0;
            while ( x % j == 0 ){
                x /= j;
                power++;
                term *= j;
            }

            if ( power % 2 )
                PP = 0;
            if ( power % 3 )
                CP = 0;

            NrDiv *= ( power + 1 );
            if ( power )
                SumaDiv *= ( ( term - 1 ) / ( j - 1 ) );
        }

        if ( x > 1 ){
            PP = CP = 0;
            NrDiv *= 2;
            SumaDiv *= ( ( x * x - 1 ) / ( x - 1 ) );
        }

        if ( NrDiv == 2 ){
            TipClatita[ciocolata]++;
            continue;
        }
        if ( PP || CP ){
            TipClatita[gem]++;
            continue;
        }
        if ( SumaDiv - i == i ){
            TipClatita[inghetata]++;
            continue;
        }
        if ( i & 1 )
            TipClatita[simpla]++;
        else
            TipClatita[zahar]++;
    }
    
    fout << M - N + 1 << "\n";

    for ( int i = 0; i < 5; ++i )
        fout << TipClatita[i] << " ";

    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 #1517 Clatite

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