题意：定义S(n) = n*各数位之积，然后给定L<=R<=10^18，求有多少个n在[L,R]区间内
思路：
看了半天无从下手。。看完题解才豁然开朗。。
具体思路看vani神博客吧。讲的很清楚。。
code：
1 #include <bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 const int maxn = 310000; 5 const ll Inf = 1000000000LL; 6 int d[maxn], dc[maxn][8], tot; 7 int td, tc[8]; 8 9 void dfs(int r, int s, ll num){ 10 if (num > Inf) return; 11 if (r == 10 || s == 18){ 12 d[tot] = num; 13 for (int i = 0; i < 8; ++i) 14 dc[tot][i] = tc[i]; 15 tot++; 16 return; 17 } 18 dfs(r + 1, s, num); 19 tc[r-2]++; 20 dfs(r, s + 1, num * r); 21 tc[r-2]--; 22 } 23 24 ll frac[25]; 25 ll count(int m){ 26 int left = m; 27 ll res = frac[m]; 28 for (int i = 0; i < 8; ++i) left -= tc[i], res /= frac[tc[i]]; 29 res /= frac[left]; 30 return res; 31 } 32 33 int bit[20]; 34 35 ll calculate(ll b, int p){ 36 if (b <= 1) return 0; 37 int k = 0; 38 while (b > 0) bit[++k] = b % 10, b /= 10; 39 int size = 0; 40 for (int i = 0; i < 8; ++i) 41 tc[i] = dc[p][i], size += tc[i]; 42 ll res = 0; 43 for (int i = 1; i < k; ++i) 44 if (i >= size) res += count(i); 45 for ( ;k > 0; --k){ 46 if (bit[k] == 0 || size > k) break; 47 for (int i = 2; i < bit[k]; ++i) if (tc[i-2]){ 48 --tc[i-2], --size; 49 if (k > size) res += count(k - 1); 50 ++tc[i-2], ++size; 51 } 52 if (bit[k] >= 2){ 53 if (k > size) res += count(k-1); 54 if (tc[bit[k]-2] == 0) break; 55 --tc[bit[k]-2], --size; 56 } 57 } 58 return res; 59 } 60 61 ll calculate(ll x){ 62 if (x <= 0) return 0; 63 ll res = 0; 64 for (int i = 0; i < tot; ++i) 65 res += calculate(x / d[i] + 1, i); 66 return res; 67 } 68 69 void pre_do(){ 70 frac[0] = 1; 71 for (int i = 1; i <= 18; ++i) frac[i] = frac[i-1] * i; 72 memset(tc, 0, sizeof(tc)); 73 tot = 0; 74 dfs(2, 0, 1); 75 } 76 77 int main(){ 78 // freopen("a.in", "r", stdin); 79 // freopen("a.out", "w", stdout); 80 pre_do(); 81 ll l, r; 82 while (cin >> l >> r){ 83 ll ans = calculate(r) - calculate(l - 1); 84 cout << ans << endl; 85 } 86 return 0; 87 }