Cod sursa(job #2260250)

Utilizator petru.ciocirlanPetru Ciocirlan petru.ciocirlan Data 14 octombrie 2018 17:56:15
Problema Sandokan Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.78 kb
#include <cstdio>

/// Vectorul ar trebui sa fie de marime minim N
int FactFreq[1000], NrFactori;

/// Schimba in long long daca valorile pot deveni foarte mari
int CombFact(int, int);
void Descompune(int, int);

int main()
{
    freopen("sandokan.in", "r", stdin);
    freopen("sandokan.out", "w", stdout);

    int N, K;

    scanf("%i %i", &N, &K);

    printf("%i\n", CombFact(N, N % K));

    return 0;
}

void Descompune(int X, int Semn)
{
    int e = 2;
    /// Cat timp poate fi descompus in factori primi (X != 1 && X > 0)
    while(X > 1)
    {
        /**
        Impartim X la e, daca se poate
        (Daca se imparte la e si nu s-a impartit la alte
         valori mai mici decat e, inseamna ca e este prim)
        **/
        int putere = 0;
        while(X % e == 0)
        {
            X /= e;
            putere++;
        }

        FactFreq[e] += Semn * putere;
        NrFactori += Semn * putere;

        /// Sarim peste numerele pare (mai putin 2 cu care incepem)
        e += 1 + (e&1);
    }
}

/// Comb(N, K) = (N!)/(K! * (N-K)!) = (N - K + 1) * (N - K + 2) * ... * N / (N - K)!
int CombFact(int N, int K)
{
    /// Descompunem (N - K + 1) * (N - K + 2) * ... * N
    /// Crestem numarul frecventelor factorilor primi (+1)
    for(int i = K + 1; i <= N; ++i)
        Descompune(i, +1);

    /// Descompunem K! = 1 * 2 * 3 * ... * K
    /// Scadem numarul frecventelor factorilor primi (-1)
    for(int i = 1; i <= N - K; ++i)
        Descompune(i, -1);

    /// Construim rezultatul final in
    /// functie de factorii primi ramasi
    int Result = 1;
    for(int i = 2; NrFactori > 0; i += 1 + (i&1))
        while(FactFreq[i])
    {
        FactFreq[i]--, NrFactori--;
        Result *= i;
    }

    return Result;
}