本文共 1604 字，大约阅读时间需要 5 分钟。
发现数字积数量很少, 枚举数字积 \(S\), 然后数位dp求数字积为 \(S\) 数的个数.
#include #include #include #include #include #include #include #include #define rep(i,l,r) for(int i=l;i<=r;++i)#define repdo(i,l,r) for(int i=l;i>=r;--i) using namespace std;typedef long long ll;typedef double db;//----------------------------------------------const int nsz=20;ll l,r,bprod;ll prod[10],v[10];ll dp[nsz][35][25][15][15];int add[10][10]={ {0,0,0,0,0}, {0,0,0,0,0}, {0,1,0,0,0}, {0,0,1,0,0}, {0,2,0,0,0}, {0,0,0,1,0}, {0,1,1,0,0}, {0,0,0,0,1}, {0,3,0,0,0}, {0,0,2,0,0}}; ll dfs(int p,ll v,ll base,ll l,ll r){ ll maxv=v+base-1; if(maxv r)return 0; if(p==0)return !(prod[1]||prod[2]||prod[3]||prod[4]); ll &tmp=dp[p][prod[1]][prod[2]][prod[3]][prod[4]]; if(l<=v&&maxv<=r&&~tmp)return tmp; ll res=0; base/=10; rep(i,(v!=0),9){ bool ok=1; rep(j,1,4)ok&=(add[i][j]<=prod[j]); if(ok==0)continue; rep(j,1,4)prod[j]-=add[i][j]; res+=dfs(p-1,v+i*base,base,l,r); rep(j,1,4)prod[j]+=add[i][j]; } if(l<=v&&maxv<=r)tmp=res; return res;} ll sol(){ bprod=sqrt(r); memset(dp,-1,sizeof(dp)); ll res=0,tmp=1; v[1]=1; rep(i,0,30){ if(i)v[1]*=2; v[2]=1; rep(j,0,20){ if(j)v[2]*=3; if(v[1]*v[2]>bprod)break; v[3]=1; rep(k,0,10){ if(k)v[3]*=5; if(v[1]*v[2]*v[3]>bprod)break; v[4]=1; rep(a,0,10){ if(a)v[4]*=7; ll tmp=v[1]*v[2]*v[3]*v[4]; if(tmp>bprod)break; prod[1]=i,prod[2]=j,prod[3]=k,prod[4]=a; res+=dfs(18,0,1e18,(l-1)/tmp+1,r/tmp); } } } } return res;}int main(){ cin>>l>>r; cout< <<'\n';}
转载于:https://www.cnblogs.com/ubospica/p/10223859.html
