Se consideră un șir de numere naturale f[1], f[2], …, f[n]. Fiecărui element al șirului i se calculează numărul biților de 1 din reprezentarea în baza 2. De exemplu, numărul 15 are 4 biți de 1 în baza 2.

Cerința

Să se determine numărul total de biți de 1 al tuturor numerelor din șir.

Date de intrare

Fișierul de intrare countbits.in conține pe prima linie numerele n, A, B, C, D, E, unde n este numărul elementelor șirului. Șirul se va genera astfel: f[1] = A, f[2] = B, apoi pentru orice i = 3..n, f[i] = 1 + (f[i-2] * C + f[i-1] * D) % E.

Date de ieșire

Fișierul de ieșire countbits.out va conține pe prima linie un singur număr, reprezentând numărul total de biți de 1 al tuturor numerelor din șir.

Restricții și precizări

3 ≤ n ≤ 15 000 000
3 ≤ A, B, C, D ≤ 100 000 000
3 ≤ E ≤ 1 000 000 000
Atenție la generarea elementelor șirului

Exemplu

countbits.in

4 7 11 15 19 8999

countbits.out

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

#include <fstream>
#define inFile  "countbits.in"
#define outFile "countbits.out"
using namespace std;

int a[32768];
/// a[i]=numarul bitilor de 1 din reprezentarea in baza 2 a lui i

void Precalc()
{
    int i, cnt, x;
    a[0] = 0;
    a[1] = 1;
    for (i = 2; i <= 32767; i++)
    {
        x = i;
        cnt = 0;
        while (x > 0)
        {
            cnt++;
            x = (x & (x - 1));
        }
        a[i] = cnt;
    }
}

int main()
{
    int i, n, A, B, C, D, E, f1, f2, f3, P;
    int cnt;
    P = (1 << 15);
    Precalc();
    ifstream fin(inFile);
    ofstream fout(outFile);
    fin >> n >> A >> B >> C >> D >> E;
    f1 = A; f2 = B;
    cnt = a[f1 % P] + a[f1 / P] + a[f2 % P] + a[f2 / P];
    for (i = 3; i <= n; i++)
    {
        f3 = 1 + (1LL*f1*C + 1LL*f2*D) % E;
        cnt += (a[f3 % P] + a[f3 / P]);
        f1 = f2;
        f2 = f3;
    }
    fout << cnt << "\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 #2487 countbits

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