Time Limit：1s Memory Limit：128MByte

Submissions：128Solved：28

Given the integers LL and RR, your task is calculating the count of the integer nn which meet the following conditions:

For instance, 11,66,1616,3636,6161,37213721 are some integers which meet the conditions.

ai是由6和1組成的數字，需要保證ai<=1e10

現在給你一個區間【l，r】，讓你求一共有多少個N，使得L<=N<=R.

這里N表示是由若干個ai相乘得到的，N<=1e10

思路：

1、觀察到T很大，明顯是要考察O（1）查詢或者是O（logn）查詢的能力。

二分查詢的考察肯定是比較套路的。

所以我萌需要進行預處理答案。

2、估計了一下，長度為1的有6和1，長度為2的有11 16 66 61.那么很明顯，預處理出從長度1到長度為10的ai.一共也就是有2046個.

那么我們接下來考慮找尋組合，使得相乘得到的數小于1e10.

我們不妨在紙上簡單的處理一些數據，不難發現，當取出來的數的個數大于等于4的時候，情況就變得非常少了。

那么我們Dfs暴力處理，做好剪枝，肯定不會超時。

這里需要注意幾點：

①我們最多可能取很多數出來，6^12的得數是小于1e10的.所以我們最多可能要取12個數。

②我們還要對數組進行去重。

③Dfs過程中處理不當可能會出現爆LL的可能，所以我們在相乘兩個數的時候，要在長度上進行預估。

3、接下來對于查詢，我們找第一個大于l的數出現的位子posl，找第一個小于r的數出現的位子posr，預處理得到的可能的N一共有6w+數，直接枚舉找位子肯定是要超時的，所以我們對這6W個數進行排序，然后二分這兩個位子，那么ans=posr-posl；

Ac代碼：

#include<bits/stdc++.h>using namespace std;#define ll long long intll ans[1000050];ll anstmp[1000050];int cnt;void Dfs(ll nw,int len){    ans[cnt++]=nw;    if(len+1<=10)    Dfs(nw*10+1,len+1);    if(len+1<=10)    Dfs(nw*10+6,len+1);}int lenn(ll a){    int re=0;    while(a)    {        a/=10;        re++;    }    return re;}void Dfs_getnum(ll nw,int ned,int hav,int pos){    if(ned==hav)    {        ans[cnt++]=nw;        return ;    }    if(pos<=2046&&nw*ans[pos]>10000000000||lenn(nw)+lenn(ans[pos])>11)return ;    for(int j=pos;j<=2046;j++)    {        if(nw*ans[j]>10000000000||lenn(nw)+lenn(ans[j])>11)break;        else        {            Dfs_getnum(nw*ans[j],ned,hav+1,j);        }    }}void init(){    cnt=0;    Dfs(1,1);    Dfs(6,1);    sort(ans,ans+cnt);    ll test=1;    for(int i=2;i<=13;i++)    {        for(int j=0;j<cnt;j++)        Dfs_getnum(ans[j],i,1,j);    }    sort(ans,ans+cnt);    for(int i=0;i<cnt;i++)anstmp[i]=ans[i];    int tmpcnt=cnt;    cnt=0;    for(int i=0;i<tmpcnt;i++)    {        if(anstmp[i]==anstmp[i+1])continue;        else        {            ans[cnt++]=anstmp[i];        }    }}int main(){    init();    int t;    scanf("%d",&t);    while(t--)    {        ll tmpl,tmpr;        scanf("%lld%lld",&tmpl,&tmpr);        int ansl=-1;        int l=0;        int r=cnt;        while(r-l>=0)        {            int mid=(l+r)/2;            if(ans[mid]>=tmpl)            {                ansl=mid;                r=mid-1;            }            else l=mid+1;        }        int ansr=-1;        l=0;        r=cnt;        while(r-l>=0)        {            int mid=(l+r)/2;            if(ans[mid]<=tmpr)            {                ansr=mid;                l=mid+1;            }            else r=mid-1;        }        if(ansl==-1||ansr==-1)        {            printf("0/n");        }        else printf("%d/n",ansr-ansl+1);    }}