#include <bits/stdc++.h> using namespace std; #define PII pair<int, int> #define VI vector<int> #define VPII vector<PII> #define LL long long #define LD long double #define f first #define s second #define MP make_pair #define PB push_back #define endl '\n' // UWAGA #define ALL(c) (c).begin(), (c).end() #define SIZ(c) (int)(c).size() #define REP(i, n) for(int i = 0; i < (int)(n); ++i) #define FOR(i, b, e) for(int i = (b); i <= (int)(e); ++i) #define FORD(i, b, e) for(int i = (b); i >= (int)(e); --i) #define random_shuffle(V) shuffle(V, rng) #define sim template<class n sim, class s> ostream & operator << (ostream &p, pair<n, s> x) {return p << "<" << x.f << ", " << x.s << ">";} sim> auto operator << (ostream &p, n y) -> typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type {int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";} void dor() {cerr << endl;} sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);} sim, class s> void mini(n &p, s y) {if(p>y) p = y;} sim, class s> void maxi(n &p, s y) {if(p<y) p = y;} #ifdef DEB #define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__) #else #define debug(...) #endif #define I(x) #x " =", (x), " " #define A(a, i) #a "[" #i " =", i, "] =", a[i], " " mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count()); int R(int a, int b) {return (int)(rng()%(b-a+1)) + a;} int RLL(LL a, LL b) {return (R(0, 1e9) * 1000 * 1000 * 1000 + R(0, 1e9)) %(b-a+1)+a;} // #pragma GCC optimize("Ofast") // while (clock()<=69*CLOCKS_PER_SEC) const int LCM = 2520; const int POT = 256; LL dp[22][LCM][POT][2]; // dim2: num % LCM dim3: for 1-9 bool if had, for 0, bool if we started writing number, // dim4: phase - 0 maeans 0 to this place, 1 means equal to this place, 2 means lower bool correct(int lcm, int mask) { FOR(i, 2, 9) if(mask & (1 << (i-2))) { if(lcm % i != 0)return 0; } return 1; } LL res(LL n) { if(n == 0)return 0; string s = to_string(n); reverse(ALL(s)); REP(i, 22) REP(j, LCM) REP(u, POT) REP(v, 2) dp[i][j][u][v] = 0; FORD(i, (int)s.size()-1, 0) { if(i + 1 == s.size())dp[i+1][0][0][0]++;// equal else dp[i+1][0][0][1]++;// less // lower REP(lc, LCM) REP(mask, POT) { FOR(num, 1, 9) { dp[i][(lc * 10 + num) % LCM][mask | (num == 1 ? 0: (1<<(num-2)))][1] += dp[i+1][lc][mask][1]; } } // equal REP(lc, LCM) REP(mask, POT) { FOR(num, 1, (int)s[i]-'0'-1) { dp[i][(lc * 10 + num) % LCM][mask | (num == 1 ? 0: (1<<(num-2)))][1] += dp[i+1][lc][mask][0]; } int num = s[i] - '0'; if(num)dp[i][(lc * 10 + num) % LCM][mask | (num == 1 ? 0: (1<<(num-2)))][0] += dp[i+1][lc][mask][0]; } } LL res = 0; REP(j, LCM) REP(u, POT) if(correct(j, u))res += dp[0][j][u][0] + dp[0][j][u][1]; return res; } int main() { ios_base::sync_with_stdio(0); LL a, b; cin >> a >> b; cout << res(b) - res(a-1) << endl; }
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 | #include <bits/stdc++.h> using namespace std; #define PII pair<int, int> #define VI vector<int> #define VPII vector<PII> #define LL long long #define LD long double #define f first #define s second #define MP make_pair #define PB push_back #define endl '\n' // UWAGA #define ALL(c) (c).begin(), (c).end() #define SIZ(c) (int)(c).size() #define REP(i, n) for(int i = 0; i < (int)(n); ++i) #define FOR(i, b, e) for(int i = (b); i <= (int)(e); ++i) #define FORD(i, b, e) for(int i = (b); i >= (int)(e); --i) #define random_shuffle(V) shuffle(V, rng) #define sim template<class n sim, class s> ostream & operator << (ostream &p, pair<n, s> x) {return p << "<" << x.f << ", " << x.s << ">";} sim> auto operator << (ostream &p, n y) -> typename enable_if<!is_same<n, string>::value, decltype(y.begin(), p)>::type {int o = 0; p << "{"; for(auto c: y) {if(o++) p << ", "; p << c;} return p << "}";} void dor() {cerr << endl;} sim, class...s> void dor(n p, s...y) {cerr << p << " "; dor(y...);} sim, class s> void mini(n &p, s y) {if(p>y) p = y;} sim, class s> void maxi(n &p, s y) {if(p<y) p = y;} #ifdef DEB #define debug(...) dor(__FUNCTION__, ":", __LINE__, ": ", __VA_ARGS__) #else #define debug(...) #endif #define I(x) #x " =", (x), " " #define A(a, i) #a "[" #i " =", i, "] =", a[i], " " mt19937 rng((unsigned int)chrono::steady_clock::now().time_since_epoch().count()); int R(int a, int b) {return (int)(rng()%(b-a+1)) + a;} int RLL(LL a, LL b) {return (R(0, 1e9) * 1000 * 1000 * 1000 + R(0, 1e9)) %(b-a+1)+a;} // #pragma GCC optimize("Ofast") // while (clock()<=69*CLOCKS_PER_SEC) const int LCM = 2520; const int POT = 256; LL dp[22][LCM][POT][2]; // dim2: num % LCM dim3: for 1-9 bool if had, for 0, bool if we started writing number, // dim4: phase - 0 maeans 0 to this place, 1 means equal to this place, 2 means lower bool correct(int lcm, int mask) { FOR(i, 2, 9) if(mask & (1 << (i-2))) { if(lcm % i != 0)return 0; } return 1; } LL res(LL n) { if(n == 0)return 0; string s = to_string(n); reverse(ALL(s)); REP(i, 22) REP(j, LCM) REP(u, POT) REP(v, 2) dp[i][j][u][v] = 0; FORD(i, (int)s.size()-1, 0) { if(i + 1 == s.size())dp[i+1][0][0][0]++;// equal else dp[i+1][0][0][1]++;// less // lower REP(lc, LCM) REP(mask, POT) { FOR(num, 1, 9) { dp[i][(lc * 10 + num) % LCM][mask | (num == 1 ? 0: (1<<(num-2)))][1] += dp[i+1][lc][mask][1]; } } // equal REP(lc, LCM) REP(mask, POT) { FOR(num, 1, (int)s[i]-'0'-1) { dp[i][(lc * 10 + num) % LCM][mask | (num == 1 ? 0: (1<<(num-2)))][1] += dp[i+1][lc][mask][0]; } int num = s[i] - '0'; if(num)dp[i][(lc * 10 + num) % LCM][mask | (num == 1 ? 0: (1<<(num-2)))][0] += dp[i+1][lc][mask][0]; } } LL res = 0; REP(j, LCM) REP(u, POT) if(correct(j, u))res += dp[0][j][u][0] + dp[0][j][u][1]; return res; } int main() { ios_base::sync_with_stdio(0); LL a, b; cin >> a >> b; cout << res(b) - res(a-1) << endl; } |