Beautiful numbers
Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer number is beautiful if and only if it is divisible by each of its nonzero digits. We will not argue with this and just count the quantity of beautiful numbers in given ranges.
Input
The first line of the input contains the number of cases t (1 ≤ t ≤ 10). Each of the next t lines contains two natural numbers li and ri (1 ≤ li ≤ ri ≤ 9 ·1018).
Please, do not use %lld specificator to read or write 64-bit integers in C++. It is preffered to use cin (also you may use %I64d).
Output
Output should contain t numbers — answers to the queries, one number per line — quantities of beautiful numbers in given intervals (from li to ri, inclusively).
Sample test(s)
input
1
1 9
output
9
input
1
12 15
output
2
题目类型:数位DP
算法分析:dp[pos][mod][lcm]表示前pos位数除以前pos位数的最小公倍数lcm余数为mod时的个数,由于1~9的最小公倍数为2520,所以mod每次可以直接对2520取模,由于1~2520中满足是最小公倍数的个数才48个,所以可以使用一个映射将最后一维的空间从2520优化到48
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 |
/************************************************* Author :supermaker Created Time :2015/12/5 21:08:41 File Location :C:\Users\abcd\Desktop\TheEternalPoet **************************************************/ #pragma comment(linker, "/STACK:102400000,102400000") #include <set> #include <bitset> #include <list> #include <map> #include <stack> #include <queue> #include <deque> #include <string> #include <vector> #include <ios> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <algorithm> #include <utility> #include <complex> #include <numeric> #include <functional> #include <cmath> #include <ctime> #include <climits> #include <cstdarg> #include <cstdio> #include <cstdlib> #include <cstring> #include <cctype> #include <cassert> using namespace std; #define CFF freopen ("aaa.txt", "r", stdin) #define CPPFF ifstream cin ("aaa.txt") #define DB(ccc) cout << #ccc << " = " << ccc << endl #define PB push_back #define MP(A, B) make_pair(A, B) typedef long long LL; typedef unsigned long long ULL; typedef double DB; typedef pair <int, int> PII; typedef pair <int, bool> PIB; const int INF = 0x7F7F7F7F; const int MOD = 1e9 + 7; const double EPS = 1e-10; const double PI = 2 * acos (0.0); const int maxn = 1e5 + 6666; LL dp[22][2666][56], bit[22], cnt[2666]; LL gcd (LL vala, LL valb) { if (valb == 0) return vala; return gcd (valb, vala % valb); } LL SS (int pos, int mod, int lcm, bool flag) { if (pos == 0) return (mod % lcm == 0); if (flag && dp[pos][mod][cnt[lcm]] != -1) return dp[pos][mod][cnt[lcm]]; LL res = 0; int x = flag ? 9 : bit[pos]; for (int i = 0; i <= x; i++) { int ta, tb; if (i == 0) ta = lcm; else ta = lcm * i / gcd (lcm, i); tb = (mod * 10 + i) % 2520; res += SS (pos - 1, tb, ta, flag || i < x); } return flag ? dp[pos][mod][cnt[lcm]] = res : res; } LL Calc (LL val) { int len = 0; while (val) { bit[++len] = val % 10; val /= 10; } return SS (len, 0, 1, 0); } int main() { //CFF; memset (dp, -1, sizeof (dp)); //CPPFF; LL t, id = 0; memset (cnt, 0, sizeof (cnt)); for (int i = 1; i <= 2520; i++) if (2520 % i == 0) cnt[i] = id++; scanf ("%I64d", &t); while (t--) { LL vala, valb; scanf ("%I64d %I64d", &vala, &valb); printf ("%I64d\n", Calc (valb) - Calc (vala - 1)); } return 0; } |
- « 上一篇:hdu4389