首页 > 代码库 > [violet2]sillyz

[violet2]sillyz

2024-07-27 18:40:24   218人阅读

 题意：定义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 }
View Code

 

[violet2]sillyz


联系
我们