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
#include <algorithm>
#include <bitset>
#include <iostream>
#include <sstream>
#include <string>
#include <vector>
using namespace std;

using MASK_t = char;

MASK_t maska_z_cyfr(string const& cyfry)
{
	MASK_t mask = 0;

	for( auto&& c : cyfry) {
		if( c < '2' ) continue;

		int poz = c - '0' - 2;
		char bit = ( 1 << poz );
		mask |= bit;
	}

	return mask;
}

struct Zadanie {
	long long const pocz;
	vector< MASK_t > dane;

	Zadanie( long long l, long long r) : pocz(l) {;
		dane.resize(r - l + 1ull, 0xFF); // USTAWIAMY MASKE NA 255 (blad)
	}

	int zlicz() {
		erastostenes(); // GASIMY BITY PODZIELNE
		cyfry();        // GASIMY BITY BEZ CYFR (ALBO ZAPALAMY WSZYTKO JESLI 0)
		return count_if(dane.begin(), dane.end(), [](char c) {return c == 0;});
	}

	void erastostenes() {
		for( int i = 2; i < 10; i++ ) {
			erastostenes(i);
		}
	}

	void erastostenes(int const dzielnik) {
		MASK_t mask1101 = ~(1 << (dzielnik - 2));
		long long reszta = pocz % dzielnik;
		long long poz = reszta ? pocz - reszta + dzielnik : pocz;

		while( poz < pocz + dane.size() ) {
			dane[ poz - pocz ] &= mask1101;
			poz += dzielnik;
		}
	}

	void cyfry() {
		for( int i = 0; i < dane.size(); ++i ) {
			MASK_t& d = dane[i];

			long long liczba = pocz + i;
			string cyfry = to_string(liczba);

			if(find_if(cyfry.begin(), cyfry.end(), [](const char c) { return c == '0'; }) != cyfry.end()) {
				d = 0xFF;
			}
			else if(d != 0) {
				char mask = maska_z_cyfr(cyfry);
				d &= mask;
			}
		}
	}
};

int main()
{
	long long l, r; cin >> l >> r;
	long long wynik = 0;

	while( l <= r ) {
		long long right = min(r, l + 1'000'000ll);
		Zadanie z(l, right);
		wynik += z.zlicz();
		l = right + 1;
	}

	cout << wynik << endl;
	return 0;
}