题目大意 : lucky number是指只含4和7的数字。very lucky number是指lucky number 和能有several个lucky number做乘积得到的数。询问一些区间[A,B](A,B<=1e12)之间very lucky number 的数量。
思路: 预先处理出所有的8000+个lucky number ,然后对这些数dfs得到范围内的所有very lucky number 。然后对于每个区间二分即可。
lucky number 只有2^12=4096个。
然后dfs。碰到乘起来超过范围的直接结束搜索。
接着利用超级屌的二分搞定。。
vector<ll> T; void dfs(int d,ll dig) { if(d>12)return; T.pb(dig); dfs(d+1,dig*10+4); dfs(d+1,dig*10+7); } int tmp; void dfs2(ll dig,int t) { if(dig!=1)T.pb(dig); for(int i=t; i<tmp; i++) { if(T[i]<=1000000000000LL/dig)dfs2(dig*T[i],i); else break; } } int lower(ll x) { if(x<T[0])return 0; if(x>=T[T.size()-1])return T.size(); int l=0,r=T.size()-1; int mid; while(l<=r) { mid=(l+r)>>1; if(T[mid]==x)return mid+1; if(x>T[mid])l=mid+1; else r=mid-1; } return min(r,mid)+1; } int main() { T.clear(); dfs(1,4); dfs(1,7); tmp=T.size(); sort(T.begin(),T.end()); dfs2(1,0); sort(T.begin(),T.end()); T.erase(unique(T.begin(),T.end()),T.end()); int TT; scanf("%d",&TT); for(int tt=1; tt<=TT; tt++) { ll a,b; scanf("%lld%lld",&a,&b); printf("Case %d: %d\n",tt,lower(b)-lower(a-1)); } return 0; }