Rozpoczęła się runda próbna tegorocznych Potyczek Algorytmicznych. O tym co można sprawdzić w rundzie próbnej napisałem w poprzedniej notce. Zwykle zadania w dniu próbnym są bardzo łatwe. Klasycznym przykładem jest zadanie w którym należy dodać dwie liczby do siebie. Ja chciałbym wrócić pamięcią dwa lata wstecz, kiedy to na dniu próbnym pojawiło się zadanie, którego nie umiałem rozwiązać.
Liczbą potyczkowa nazywamy każdą liczbę, która jest podzielna przez wartości wszystkich swoich cyfr. Należy znaleźć liczbę wszystkich liczb potyczkowa w przedziale [L; R]. Liczby L, R są mniejsze od 1018, więc sprawdzanie każdej z liczb z osobno można szybko sobie wybić z głowy.
Podstawy teorii liczb
Zacznijmy od przypomnienia, że liczba jest podzielna przez a oraz przez b wtedy i tylko wtedy, gdy jest podzielna przez Najmniejszą Wspólną Wielokrotność a i b. Dla przykładu: liczba jest podzielna przez 4 i przez 6 wtedy i tylko wtedy gdy jest podzielna przez 12. Od teraz będziemy sprawdzać jedynie czy liczba jest podzielna przez Najmniejszą Wspólną Wielokrotność wartości wszystkich swoich cyfr.
Jest 48 różnych liczb, które mogą być Najmniejszą Wspólną Wielokrotnością wszystkich cyfr w pewnej liczbie. Liczby te są postaci 2a x 3b x 5c x 7d gdzie a ∊ {0, 1, 2, 3}, b ∊ {0, 1, 2}, c ∊ {0, 1} i d ∊ {0, 1}. Aby sprawdzić czy liczba jest podzielna przez którąkolwiek z tych liczb, wystarczy nam informacja, jaka jest reszta z dzielenia tej liczby przez NWW wszystkich tych liczb (czyli przez 2520). Dla przykładu: jeśli liczba przy dzieleniu przez 2520 daję resztę 360, a NWW jej cyfr wynosi 30, to jest ona liczbą potyczkowa, bo 360 mod 30 = 0.
Rozgrzewka – programowanie dynamiczne
Policzmy ile jest k-cyfrowych liczb potyczkowa. Definiujemy następującą wartość:
DP[k][NWW][MOD] – liczba k-cyfrowych liczb, których Najmniejsza Wspólna Wielokrotność wartości poszczególnych cyfr jest równa NWW i która daje resztę z dzielenia przez 2520 równą MOD.
Zauważmy, że mając policzone takie wartości, jesteśmy w stanie łatwo policzyć liczbę k-cyfrowych liczb potyczkowa. Realizuje to poniższy algorytm:
long long get_result(int k)
{
long long cnt = 0;
for (int nww = 0; nww < 48; nww++)
for (int mod = 0; mod < 2520; mod++)
if (mod % nww_values[nww] == 0)
cnt += DP[k][nww][mod];
return cnt;
}gdzie nww_values to bijekcja (funkcja różnowartościowa) przekształcająca liczby 0-47 na jedną z 48 możliwych Najmniejszych Wspólnych Wielokrotności wartości cyfr. Algorytm można napisać w odrobinę optymalniejszy sposób:
long long get_result(int k)
{
long long cnt = 0;
for (int nww = 0; nww < 48; nww++)
for (int mod = 0; mod < 2520; mod += nww_values[nww])
cnt += DP[k][nww][mod];
return cnt;
}Pozostaje nam policzenie tych wartości. Powiedzmy, że mamy pewną 5-cyfrową liczbę, której Najmniejsza Wspólna Wielokrotność wartości cyfr jest równa 10 oraz daje resztę z dzielenia przez 2520 równą 325. Jeśli dokleimy do niej cyfrę 7 na koniec, otrzymamy liczbę 6-cyfrową, której Najmniejsza Wspólna Wielokrotność wartości cyfr jest równa NWW(10, 7) = 70 oraz daje resztę z dzielenia przez 2520 równą (325 * 10 + 7) mod 2520 = 737. Innymi słowy – do policzenia DP[k][*][*] wystarczy nam znajomość wartości DP[k-1][*][*]. Możemy użyć pętli for po każdej cyfrze, którą możemy dokleić (od 1 do 9) aby policzyć wartości dla DP[k][*][*]. Ideę tą implementuje poniższy kod.
long long DP[3][48][2520];
void calc(int max_k)
{
DP[0][nww_index[1]][0] = 1;
for (int k = 1; k <= max_k; k++)
for (int nww = 0; nww < 48; nww++)
for (int mod = 0; mod < 2520; mod++)
for (int cyfra = 1; cyfra <= 9; cyfra++)
{
int new_nww = nww_index[lcm(nww_values[nww], cyfra)];
int new_mod = (10 * mod + cyfra) % 2520;
DP[k][new_nww][new_mod] += DP[k-1][nww][mod];
}
}gdzie nww_index to funkcja odwrotna do nww_values, a lcm (least common multiplication) to funkcja licząca NWW. To była łatwiejsza część zadania.
Liczba liczb potyczkowa <= b
W tym rozdziale spróbujemy zmusić algorytm, aby policzył liczbę liczb potyczkowa, mniejszych bądź równych pewnej ustalonej liczby b. Zrobimy to modyfikując algorytm z poprzedniej sekcji. Dla przykładu weźmy b = 345.
W poprzednim algorytmie zaczęliśmy od k = 1. Tutaj sprawa jest dość prosta. Wystarczy zmodyfikować algorytm tak, aby zamiast przeglądać wszystkie cyfry, przeglądał jedynie te, mniejsze od pierwszej cyfry w liczbie b. W naszym przykładzie są to cyfry 1, 2 oraz 3.
Jeśli liczba b byłaby jednocyfrowa, to na tym byśmy zakończyli. Schody zaczynają się już dla k = 2. Jeśli teraz też ograniczylibyśmy liczbę cyfr, to nie policzylibyśmy wszystkich liczb. Dla przykładu, jeśli rozważymy cyfry 1, 2, 3 i 4 to w sumie zliczymy liczby 11, 12, 13, 14, 21, 22, 23, 24, 31, 32, 33 oraz 34. Pominęliśmy 15,16,17,18,19, 25, 26, 27, 28, 29.
Nie możemy również po prostu przejść po wszystkich cyfrach. Jeśli tak byśmy zrobili, to policzylibyśmy liczby 35, 36, 37, 38 oraz 39, które są większe od 34.
Musimy połączyć oba pomysły ze sobą. Do liczb 1 oraz 2 dokładamy każdą z cyfr 1 – 9, a do liczby 3 tylko cyfry 1-4.
void calc(long long b)
{
vector<int> cyfry = int_to_vector(b);
int max_k = cyfry.size();
int prefix_nww = 1;
int prefix_mod = 0;
for (int k = 1; k <= max_k; k++)
{
// Dodajemy 1-9 do pozostałych liczb
for (int nww = 0; nww < 48; nww++)
for (int mod = 0; mod < 2520; mod++)
for (int cyfra = 1; cyfra <= 9; cyfra++)
{
int new_nww = nww_index[lcm(nww_values[nww], cyfra)];
int new_mod = (10 * mod + cyfra) % 2520;
DP[k][new_nww][new_mod] += DP[k-1][nww][mod];
}
// Dodajemy 1-x do prefiksu liczby
for (int cyfra = 1; cyfra < cyfry[k-1]; cyfra++)
{
int new_nww = nww_index[lcm(prefix_nww, cyfra)];
int new_mod = (10 * prefix_mod + cyfra) % 2520;
DP[k][new_nww][new_mod]++;
}
prefix_nww = lcm(prefix_nww, cyfry[k-1]);
prefix_mod = (10 * prefix_mod + cyfry[k-1]) % 2520;
}
DP[max_k][nww_index[prefix_nww]][prefix_mod]++;
}Powyższy kod liczy ile jest liczb potyczkowa mniejszych od b, ale mających tyle samo cyfr co b. Do pełni szczęścia pozostaje nam jeszcze policzenie ile jest liczb potyczkowa, które mają mniej cyfr niż b. Można to zrobić korzystając z algorytmu z poprzedniego rozdziału, albo dodając jedną linijkę do kodu powyżej. Na koniec pozostaje nam załatać spory problem w naszym kodzie. Otóż nasz program zakłada, że w liczbie b nie znajduje się cyfra 0. Trzeba wyifować przypadek kiedy napotykamy cyfrę 0 w liczbie b.
Rozwiązanie zadania
Już myślałeś, że to koniec? W zadaniu chodziło o to, aby znaleźć liczbę liczb potyczkowa w przedziale [L; R]. Na razie nasz program liczy liczbę liczb potyczkowa z przedziału [1; R]. Na szczęście łatwo jest zmodyfikować algorytm, aby liczył przedział o który nam chodzi. Jak? Zostawiam to pytanie już Czytelnikowi.
