Zadanie

“Čau Radka, už si sa začala učiť na maturity?” ozvalo sa zo slúchadla.

“Blázniš?! Však je polka leta. Aktuálne ma trápi iba to, ako budem čo najdlhšie spať, a kde sa pôjdem kúpať.”

“No hej… Ale vieš, že tohtoročné maturity pripravuje Žaba. To nebude také ľahké. A ak chceš aby ťa zobrali na informatiku na najlepšej škole – matfyze1 – bez prijímačiek, musíš mať z maturity 1.”

“Prosím ťa. Na to aby ťa zobrali na matfyz stačí byť úspešným riešiteľom olympiády v informatike, teda získať 10 zo 40 bodov. Malina. A ešte sa na dva dni uleješ zo školy. Aj ty by si sa mala tento rok zapojiť, Rebeka.”

“Okrem toho,” pokračovala Radka, “videla som jedno z nových maturitných zadaní. Spočítaj ciferný súčet zadaného čísla2. Mala som to naprogramované za 3 minúty. Však pozri, poslala som ti kód v správe.”

“Počuj, Radka,” opáči Rebeka. “Určite to máš dobre? Však tam máš * namiesto +.”

“Ale však na všetkých vstupoch to fungovalo. Pre 22 vráti 4. Pre 1142 číslo 8…”

“No hej, ale mám pocit, že to je skôr náhoda. Však pre 33 vypíšeš 9, ale správne by to malo byť 6.”

“Hmmm… máš pravdu. Ale aj tak, skúšala som si to na fakt veľa vstupoch a vždy to dávalo správne výsledky.”

“Asi preto, že sa ti vždy podarilo trafiť číslo, ktorého ciferný súčet aj súčin sú rovnaké. Mala si len šťastie, alebo je takých čísel ozaj tak veľa?” zaujímalo Rebeku.

“Neviem, ale určite sa to dá vypočítať!”

Úloha

Samozrejme, čísel, ktoré majú rovnaký ciferný súčet aj súčin je nekonečne veľa. A ak to samozrejmé nie je, tak si to skúste rozmyslieť. Zistovať ich počet by preto nebola zaujímavá KSP úloha. Zaujímavé je ale zisťovať, koľko prirodzených čísel má ciferný súčet aj súčin rovný číslu \(n\).

Formát vstupu

Na jedinom riadku vstupu je zadané číslo \(n\). V ôsmych testovacích sadách platia pre toto číslo nasledovné obmedzenia:

Sada 1 2 3 4 5 6 7 8
\(n \leq\) \(10\) \(100\) \(500\) \(1\,000\) \(50\,000\) \(100\,000\) \(300\,000\) \(300\,000\)

Formát výstupu

Na výstup vypíšte jedno číslo – počet prirodzených čísel, ktorých ciferný súčet aj ciferný súčin je rovný číslu \(n\). Keďže takýchto čísel môže byť naozaj veľa, vypíšte ich počet modulo \(10^9 + 7\).

Príklad

Input:

4

Output:

2

Dve čísla, ktorých ciferný súčet aj súčin je 4 sú čísla 22 a 4.

Input:

8

Output:

23

Jednou z možností je číslo 1142.

Input:

72

Output:

100110164

  1. https://fmph.uniba.sk/studium/prijimacie-konanie/univerzitna-elektronicka-prihlaska/

  2. Samozrejme, že Žaba by takúto ľahkú maturitnú otázku nepripravil. Čo je mäkký? Jeho maturanti budú musieť poznať aj Mersenove prvočísla.

Na začiatok si uvedomme, že ciferný súčin nám dáva akýsi rozklad čísla \(n\) na súčin, ktorého každý člen tvorí samostatná cifra. To ale znamená, že v prvočíselnom rozklade čísla \(n\) (čo je jemnejší rozklad) sa môžu nachádzať iba prvočísla menšie ako 10. V opačnom prípade číslo s daným ciferným súčinom neexistuje a odpoveď je 0.

Neprvočíselné cifry a ciferný súčet

Medzi ciframi našeho čísla sa môžu nachádzať aj neprvočíselné hodnoty, preto nám rozklad \(n\) na prvočísla nedá jednoznačnú sadu cifier, ktorú musíme použiť. Toto sa týka cifier 4, 6, 8 a 9, v našom riešení sa preto budeme musieť rozhodnúť, koľko prvočísel 2 a 3 použijeme na ich vytváranie. Presnejšie, budeme sa musieť rozhodnúť, koľko cifier 4, 6, 8 a 9 chceme mať vo výslednom čísle.

Zabudnúť nemôžeme ani na druhú podmienku zadania – ciferný súčet, ktorý sa tiež musí rovnať \(n\). Ciferný súčet je však väčšinou oveľa menší ako súčin, číslo preto vieme doplniť potrebným počtom cifier 1, ktoré ciferný súčin nemenia.

Ako vybrať sadu použitých cifier?

Koľko možností máme na výber počtu jednotlivých cifier? Vieme napríklad, že nemôžeme použiť žiadnu cifru 0, pretože celý ciferný súčin by bol tiež 0. A keďže poznáme prvočíselný rozklad \(n\), vieme, že naše číslo musí obsahovať rovnaký počet 5 a 7 ako je v tomto rozklade. Otázne sú iba cifry 4, 6, 8 a 9, keby sme vedeli, koľko ich bude vo výsledku, počet 2 a 3 si vieme dopočítať z celkového počtu týchto čísel v rozklade.

Skúsime teda všetky možnosti, lebo vieme, že maximálny počet jednej cifry môže byť najviac \(\log n\), keďže ich súčin nesmie presiahnuť hodnotu \(n\). Určením týchto cifier sú už všetky ostatné jednoznačne dané, počet 1 dopočítame tak, aby sedel ciferný súčet (ak by nám tento počet vyšiel záporný, tak počty ostatných cifier nevyhovujú žiadnemu číslu).

Koľko možných čisiel máme pre danú sadu cifier?

Keď už vieme koľko jednotlivých cifier chceme použiť v našom čísle, potrebujeme zvoliť ich poradie. To totiž nemení ciferný súčet ani súčin, chceme preto zarátať všetky možné preusporiadania. Toto je už však pomerne ľahká kombinatorická úloha, ak si počet cifry \(i\) označíme ako \(P_i\) a počet všetkých cifier dokopy ako \(x\), počet preusporiadaní je:

\[\binom{x}{P_1} \binom{x-P_1}{P_2} ... \binom{x-P_1- ... - P_8}{P_9} = \frac{x!}{P_1! P_2! ... P_9!}\].

Na daný vzorec sa môžete pozerať cez kombinačné čísla (ľavá strana), keď si postupne volíme na ktoré pozície dáme ktoré cifry a počet voľný pozícií sa zmenšuje, alebo ako na permutácie s opakovaním (pravá strana), kde najskôr započítame všetky možné preusporiadania a potom odstraňujeme (delíme) tie, kde sme iba zmenili poradie rovnakých cifier.

Celkový počet cifier bude kvôli cifernému súčtu určite najviac \(n\) a preto si vieme predpočítať všetky faktoriály až po hodnotu \(x\) dopredu a to dokonca modulo \(10^9+7\). Tu však nastáva problém, pretože v okamihu, keď začneme čísla modulovať, normálne delenie prestane správne fungovať. Našťastie, na vyriešenie tohto problému poznáme pomerne klasickú techniku inverzných prvkov. Pre každý faktoriál si vypočítame aj jeho inverzný prvok a keď týmto faktoriálom potrebujeme deliť, namiesto toho delené číslo vynásobíme inverzným prvkom delenca. Keďže hodnota \(p=10^9+7\), ktorú používame na modulovanie je prvočíslo platí, že inverzný prvok čísla \(a\) je rovný \(a^{p-2}\).

V prípade, že sa chcete o inverzných prvkoch dozvedieť niečo viac, prečo ich potrebujeme a počítame práve daným spôsobom, navštívte našu kuchárku a prečítajte si článok o Počítaní modulo prvočíslo.

Časová a pamäťová zložitosť

Najprv si potrebujeme predpočítať všetky faktoriály a ich inverzy, čo nám zaberie \(O(n \log p)\) času (\(p = 10^9+7\)), keďže na vypočítanie inverzu čísla ho musíme umocniť na \(p-2\), čo vieme spraviť v logaritmickom čase. Následne musíme vygenerovať všetky možné počty cifier 4, 6, 8 a 9, každej z nich môže byť najviac \(O(\log n)\), čo dáva dokopy zložitosť \(O(\log^4 n)\). Počty týchto cifier jednoznačne určujú počty zvyšných cifier, ostáva teda výpočet všetkých preusporiadaní vybranej sady cifier. To vieme spraviť v konštantnom čase, keďže faktoriály a ich inverzy už máme predpočítané. Celková časová zložitosť našeho riešenia je \(O(n \log p)\).

V pamäti musíme mať predrátané všetky faktoriály, teda pamäťová zložitosť bude \(O(n)\)

#include <bits/stdc++.h>
using namespace std;

#define For(i,n) for(int i=0; i<(n); i++)

typedef long long ll;

int n;
ll res=0, MOD = 1000000007;

vector<int> P;
vector<ll> F, I;

ll umocni(ll a, ll b) {
    ll res1=1;
    while(b>0) {
        if(b%2 == 1) res1=(res1*a)%MOD;
        a=(a*a)%MOD;
        b/=2;
    }
    return res1;
}

void init() {
    F.push_back(1);
    for(int i=1; i<300047; i++) F.push_back((F[i-1]*i)%MOD);
    For(i, F.size()) I.push_back(umocni(F[i],MOD-2));
}

void rek(int maxi) {
    if(maxi <= 4 && P[2] >= 2) {
        P[2]-=2; P[4]++;
        rek(4);
        P[2]+=2; P[4]--;
    }
    if(maxi <= 6 && P[2] >= 1 && P[3] >= 1) {
        P[2]--; P[3]--; P[6]++;
        rek(6);
        P[2]++; P[3]++; P[6]--;
    }
    if(maxi <= 8 && P[2] >= 3) {
        P[2]-=3; P[8]++;
        rek(8);
        P[2]+=3; P[8]--;
    }
    if(maxi <= 9 && P[3] >= 2) {
        P[3]-=2; P[9]++;
        rek(9);
        P[3]+=2; P[9]--;
    }
    P[1]=n;
    for(int i=2; i<=9; i++) P[1]-=i*P[i];
    if(P[1] < 0) return;
    int suc=0;
    For(i,10) suc+=P[i];
    ll pocet = F[suc];
    For(i,10) {
        pocet = (pocet * I[P[i]]) % MOD;
    }
    res = (res+pocet)%MOD;
}

int main() {
    init();
    scanf(" %d",&n);
    P.clear();
    P.resize(10,0);
    int p=n;
    for(int i=2; i<=9; i++) {
        while(p%i == 0) {
            P[i]++;
            p/=i;
        }
    }
    if(p != 1) {
        printf("0\n");
        return 0;
    }
    res=0;
    rek(0);
    printf("%lld\n",res);
}

Diskusia

Tu môžte voľne diskutovať o riešení, deliť sa o svoje kusy kódu a podobne.

Pre pridávanie komentárov sa musíš prihlásiť.