Rezolvare completă PbInfo #2166 numere19

Fie a și b două numere naturale nenule.

Cerința

Scrieți un program care determină numărul de numere naturale formate din exact a cifre care au fiecare produsul cifrelor egal cu b și afișează în fișierul de ieșire restul împărțirii valorii determinate la numărul 9973.

Date de intrare

Fișierul de intrare numere19.in conține pe prima linie numerele a și b despărțite printr-un spațiu.

Date de ieșire

Fișierul de ieșire numere19.out va conține pe prima linie o singură valoare care reprezintă restul împărțirii numărului de numere naturale formate din exact a cifre care au produsul cifrelor egal cu b la 9973.

Restricții și precizări

  • Pentru 10% din teste 1 ≤ a ≤ 6, 1 ≤ b ≤ 1000
  • Pentru 20% din teste 7 ≤ a ≤ 150, 1 ≤ b ≤100
  • Pentru 30% din teste 151 ≤ a ≤1000, 1≤ b ≤ 100
  • Pentru 40% din teste 1001 ≤ a ≤9000, 100≤ b ≤ 9000

Exemplul 1:

numere19.in

3 9

numere19.out

6

Explicație

Cele șase numere sunt: 119, 133, 191, 313, 331, 911

Exemplul 2:

numere19.in

4 15

numere19.out

12

Explicație

Cele 12 numere sunt: 1135, 1153, 1315, 1351, 1513, 1531, 3115, 3151, 3511, 5113, 5131, 5311

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

#include <bits/stdc++.h>
#define MOD 9973
using namespace std;
int n, P, nrsol;
int a[10], k;   /// retin cifrele divizibile cu P
int e[10];      /// retin exponentii pentru a[i]
int fact[9001]; /// fact[i] = i! % MOD
int st[10];     /// stiva pentru back

void Citire()
{
    ifstream fin("numere19.in");
    fin >> n >> P;
    fin.close();
}

void Constructie()
{
    int i, x;
    for(i = 2; i <= 9; i++)
        if(P % i == 0)
        {
            a[++k] = i;
            x = P;
            while(x % i == 0)
            {
                e[k]++;
                x /= i;
            }
        }
}

void Factorial()
{
    int i;
    fact[1] = 1;
    for(i = 2; i <= 9000; i++)
        fact[i] = (fact[i - 1] * i) % MOD;
}

int LogPut(int x, int n)
{
    int s = 1;
    while(n > 0)
    {
        if(n % 2 == 1)
        {
            s = (s * x) % MOD;
            n--;
        }
        n /= 2;
        x = (x * x) % MOD;
    }
    return s;
}

int Valid(int top,int x)
{
    int prod, i, j;
    prod = 1;
    for (i = 1; i < top; i++)
        if (st[i] != 0)
          for (j = 1; j <= st[i]; j++)
            prod *= a[i];
    for (i = 1; i <= x; i++)
        prod *= a[top];
    if (prod > P) return 0;
    if (top == k && prod != P) return 0;
    return 1;
}

void Solutie()
{
    int i, s ,t[10], m, cnt, x;
    s = 0;
    for(i = 1; i <= k; i++)
        s += st[i];
    if (s > n) return;
    m = 0;
    for(i = 1; i <= k; i++)
        if(st[i] > 1)
            t[++m]=st[i];
    if(n - s > 1)
        t[++m] = n - s;
    cnt = fact[n];
    for(i = 1; i <= m; i++)
    {
        x = LogPut(fact[t[i]], MOD - 2);
        cnt = (cnt * x) % MOD;
    }
    nrsol += cnt;
}

void Back(int top)
{
    int i;
    if(top == k + 1) Solutie();
    else
    {
        for(i = 0; i <= e[top]; i++)
            if(Valid(top, i))
            {
                st[top] = i;
                Back(top + 1);
            }
    }
}

void Afisare()
{
    ofstream fout("numere19.out");
    nrsol = nrsol % MOD;
    fout << nrsol << "\n";
    fout.close();
}

int main()
{
    Citire();
    Factorial();
    Constructie();
    Back(1);
    Afisare();
    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 #2166 numere19

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