1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <bits/stdc++.h>
using namespace std;

// 10^18 -> 19 cyfr
const int MAX_DLUGOSC = 19;
// LCM(1, ..., 9) = 2520
const int LCM_CYFR = 2520;
// LCM(1, ..., 9) ma 48 dzielnikow
const int DZIELNIKI = 48;

int cyfry[MAX_DLUGOSC];
int indeks[LCM_CYFR + 1];
long long dp[MAX_DLUGOSC][DZIELNIKI][LCM_CYFR / 10];

int LCM(int a, int b)
{
	return a * b / __gcd(a, b);
}

// pozycja to numer cyfry, liczac od najmniej znaczacych cyfr, danej liczby
// lcm to LCM cyfr danej liczby
// suma to reszta z dzielenia danej liczby przez LCM_CYFR
// wyczerpane mowi czy mamy liczbe scisle mniejsza od liczby, ktora jest gornym limitem
// wyczerpane jest prawdziwe, jesli na wszystkich pozycjach na lewo (bardziej znaczacych) mamy juz maksymalne cyfry
// zero jest prawdziwe, jesli dana liczba ma zera wiodace
long long DFS(int pozycja, int lcm, int suma, bool wyczerpane, bool zero)
{
	// przypadek kiedy na wszystkich pozycjach sa juz cyfry
	if(pozycja == -1)
	{
		return suma % lcm == 0;
	}

	// jesli juz cos wczesniej policzylismy, to skorzystajmy z tego
	if(!wyczerpane && dp[pozycja][indeks[lcm]][suma] != -1)
	{
		return dp[pozycja][indeks[lcm]][suma];
	}

	long long ans = 0;

	int maksymalna_cyfra;

	// jesli wyczerpane to mozemy dodac tylko liczby z przedzialu 0, ..., cyfra[pozycja]
	if(wyczerpane)
	{
		maksymalna_cyfra = cyfry[pozycja];
	}

	// mozemy dodac dowolna liczbe z przedzialu 0, ..., 9
	else
	{
		maksymalna_cyfra = 9;
	}

	for(int cyfra = 0; cyfra <= maksymalna_cyfra; cyfra++)
	{
		int nowy_lcm;

		bool nowe_zero = zero;

		if(cyfra > 0)
		{
			nowy_lcm = LCM(lcm, cyfra);

			nowe_zero = false;
		}

		else
		{
			nowy_lcm = lcm;

			// sprawdzamy, czy dodajemy zero wiodace
			nowe_zero &= true;
		}

		int nowa_suma = suma * 10 + cyfra;

		// Zeby stwierdzic podzielnosc przez 2 lub 5 potrzebujemy tylko ostatniej cyfry liczby
		// W takim przypadku pozostale cyfry nie maja wplywu na podzielnosc
		// A wiec jesli dokladamy liczbe na innej pozycji niz pierwsza (pozycja jednosci), to mozemy zrobic suma %= 252
		if(pozycja > 0)
		{
			nowa_suma %= 252;
		}

		// jesli dokladamy cyfre inna niz 0 lub jesli dokladamy 0 z przodu (skracamy liczbe o 1 pozycje)
		if(cyfra != 0 || (cyfra == 0 && nowe_zero))
		{
			ans += DFS(pozycja - 1, nowy_lcm, nowa_suma, wyczerpane && (cyfra == maksymalna_cyfra), nowe_zero);
		}
	}

	if(!wyczerpane)
	{
		dp[pozycja][indeks[lcm]][suma] = ans;
	}

	return ans;
}

long long solve(long long liczba)
{
	int dlugosc = 0;
	
	while(liczba)
	{
		cyfry[dlugosc] = liczba % 10;

		dlugosc++;

		liczba /= 10;
	}

	return DFS(dlugosc - 1, 1, 0, true, true);
}

void preprocessing()
{
	int ilosc_dzielnikow = 0;

	for(int i = 1; i <= LCM_CYFR; i++)
	{
		if(LCM_CYFR % i == 0)
		{
			indeks[i] = ilosc_dzielnikow;

			ilosc_dzielnikow++;
		}
	}

	memset(dp, -1, sizeof(dp));
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

	long long L, R;
	cin >> L >> R;

	preprocessing();

	cout << solve(R) - solve(L - 1) << "\n";
	return 0;
}