首页 > 代码库 > [violet2]sillyz
[violet2]sillyz
题意:定义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 }
[violet2]sillyz
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。