#include <iostream> #include <vector> #include <algorithm> using namespace std; const int lcm = 2520; uint64_t tb[18][lcm][1<<8]; bool ok[lcm][1<<8]; void preprocess() { tb[0][0][0] = 1; for(int d = 1; d < 18; ++d) { for(int r = 0; r < lcm; ++r) { for(int m = 0; m < (1<<8); ++m) { int new_rem = (r*10+1)%lcm; tb[d][new_rem][m] += tb[d-1][r][m]; for(int nd = 2; nd < 10; ++nd) { new_rem = (r*10+nd)%lcm; const int new_dig = m | (1<<(nd-2)); tb[d][new_rem][new_dig] += tb[d-1][r][m]; } } } } for(int r = 0; r < lcm; ++r) { for(int m = 0; m < (1<<8); ++m) { bool isok = true; for(int d = 0; d < 8; ++d) { if((m & (1<<d)) && r%(d+2) > 0) { isok = false; break; } } ok[r][m] = isok; } } } uint64_t getCountDigits(uint64_t front, int front_mask, int backDigits) { uint64_t count = 0; uint64_t tens = 1; for(int i = 0; i < backDigits; ++i) { tens *= 10; } for(int r = 0; r < lcm; ++r) { for(int m = 0; m < (1<<8); ++m) { const uint64_t new_rem = (front * tens + r)%lcm; const int new_mask = m | front_mask; if(ok[new_rem][new_mask]) { count += tb[backDigits][r][m]; } } } return count; } uint64_t getCount(uint64_t n) { vector<int> digits; while(n > 0) { digits.push_back(n%10); n /= 10; } reverse(digits.begin(), digits.end()); uint64_t count = 0; uint64_t front = 0; int mask = 0; for(int i = digits.size()-1; i >= 1; --i) count += getCountDigits(0, mask, i); for(int i = 0; i < digits.size(); ++i) { for(int digit = 1; digit < digits[i]; ++digit) { const uint64_t new_front = front*10+digit; uint64_t new_mask = mask; if(digit >= 2) { new_mask = mask | (1<<(digit-2)); } count += getCountDigits(new_front, new_mask, digits.size()-i-1); } front = front*10+digits[i]; if(digits[i] == 0) { break; } if(digits[i] > 1) { mask |= (1<<(digits[i]-2)); } } return count; } int main() { preprocess(); uint64_t l, r; cin >> l >> r; cout << getCount(r+1) - getCount(l) << '\n'; }
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 | #include <iostream> #include <vector> #include <algorithm> using namespace std; const int lcm = 2520; uint64_t tb[18][lcm][1<<8]; bool ok[lcm][1<<8]; void preprocess() { tb[0][0][0] = 1; for(int d = 1; d < 18; ++d) { for(int r = 0; r < lcm; ++r) { for(int m = 0; m < (1<<8); ++m) { int new_rem = (r*10+1)%lcm; tb[d][new_rem][m] += tb[d-1][r][m]; for(int nd = 2; nd < 10; ++nd) { new_rem = (r*10+nd)%lcm; const int new_dig = m | (1<<(nd-2)); tb[d][new_rem][new_dig] += tb[d-1][r][m]; } } } } for(int r = 0; r < lcm; ++r) { for(int m = 0; m < (1<<8); ++m) { bool isok = true; for(int d = 0; d < 8; ++d) { if((m & (1<<d)) && r%(d+2) > 0) { isok = false; break; } } ok[r][m] = isok; } } } uint64_t getCountDigits(uint64_t front, int front_mask, int backDigits) { uint64_t count = 0; uint64_t tens = 1; for(int i = 0; i < backDigits; ++i) { tens *= 10; } for(int r = 0; r < lcm; ++r) { for(int m = 0; m < (1<<8); ++m) { const uint64_t new_rem = (front * tens + r)%lcm; const int new_mask = m | front_mask; if(ok[new_rem][new_mask]) { count += tb[backDigits][r][m]; } } } return count; } uint64_t getCount(uint64_t n) { vector<int> digits; while(n > 0) { digits.push_back(n%10); n /= 10; } reverse(digits.begin(), digits.end()); uint64_t count = 0; uint64_t front = 0; int mask = 0; for(int i = digits.size()-1; i >= 1; --i) count += getCountDigits(0, mask, i); for(int i = 0; i < digits.size(); ++i) { for(int digit = 1; digit < digits[i]; ++digit) { const uint64_t new_front = front*10+digit; uint64_t new_mask = mask; if(digit >= 2) { new_mask = mask | (1<<(digit-2)); } count += getCountDigits(new_front, new_mask, digits.size()-i-1); } front = front*10+digits[i]; if(digits[i] == 0) { break; } if(digits[i] > 1) { mask |= (1<<(digits[i]-2)); } } return count; } int main() { preprocess(); uint64_t l, r; cin >> l >> r; cout << getCount(r+1) - getCount(l) << '\n'; } |