<h1 id="heading">题目</h1>
<p>{% raw %}</p>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐题目</div></div><div class="fold">
    <div class="oj">   
        <div class="part" title="Description">
{% endraw %}
数字的每一位只可能是4或者7的称为幸运数，比如说4，7，44，474，7474都是幸运数，而54，40，444467777都不是幸运数。而数字A的下一个幸运数，表示的是大于等于A的最小的幸运数。比如4的下一个幸运数是4，而5的下一个幸运数是7。现在给出一个区间[L, R]，求出区间内每个数的下一个幸运数的和。  
<p>{% raw %}<br>
</div><br>
<div class="part" title="Input"><br>
{% endraw %}</p>
<p>一个整数t，表示测试数据的组数(1&lt;=t&lt;=200)。<br>
每组测试数据，两个整数L和R，空格隔开(1&lt;=L&lt;=R&lt;=1000000000)。</p>
<p>{% raw %}<br>
</div><br>
<div class="part" title="Output"><br>
{% endraw %}</p>
<p>区间内每个数的下一个幸运数的和</p>
<p>{% raw %}<br>
</div><br>
<div class="samp"><br>
<div class="clear"></div><br>
<div class="input part" title="Sample Input"><br>
{% endraw %}</p>
<p>3<br>
4 4<br>
3 4<br>
4 7</p>
<p>{% raw %}<br>
</div><br>
<div class="output part" title="Sample Output"><br>
{% endraw %}</p>
<p>4<br>
8<br>
25</p>
<p>{% raw %}<br>
</div><br>
<div class="clear"></div><br>
</div><br>
</div></p>
</div></div>
{% endraw %}

<h1 id="heading-1">题解</h1>
<p>找到 <code>[l,r]</code> 范围内所有的所有整数的 <strong>下一个幸运数</strong><br>
很显然,<strong>幸运数是非常少的</strong><br>
将 <code>4</code> 和 <code>7</code> 看作 <code>0</code> 和 <code>1</code><br>
可以发现数量只有 {% raw %}$ log_2 1000000000 ${% endraw %} 个<br>
然后打个表,二分查找 <code>l</code> 和 <code>r</code> 两侧的幸运数,每两个幸运数为一个区间(最两侧端点是 <code>l</code> 和 <code>r</code>)<br>
然后计算求和即可<br>
<strong>不用一个一个加,区间端点相减乘以右端点即可</strong></p>
<p>最后测试的时候,应该对于  <code>l</code> 和 <code>r</code> 都测试下比幸运数小 <code>1</code> 大 <code>1</code> 相等的情况<br>
也即最后测试 <code>6</code> 组即可<br>
顺便测试下极端值也行(为了保证极端值没问题,<strong>打表要打到比最大值大</strong>)</p>
<h1 id="heading-2">代码</h1>
<div><div class="fold_hider"><div class="close hider_title">点击显/隐代码</div></div><div class="fold">```cpp 下一个幸运数 https://github.com/OhYee/sourcecode/tree/master/ACM 代码备份
/*/
#define debug
#include <ctime>
//*/
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
<p>typedef unsigned long long LL;<br>
const int maxn = 5000;<br>
LL L[maxn];<br>
int pos=0;</p>
<p>void dfs(LL t){<br>
if(t &gt;= 7777777777LL)<br>
return;<br>
L[pos++] = t<em>10+4;<br>
L[pos++] = t</em>10+7;<br>
dfs(t<em>10+4);<br>
dfs(t</em>10+7);<br>
}</p>
<p>LL lower_bound(LL *arr,int size, LL key) {<br>
int half;<br>
int mid;<br>
int first = 0;<br>
while (size &gt; 0) {<br>
half = size &gt;&gt; 1;<br>
mid = first + half;<br>
if (arr[mid] &lt; key) {<br>
first = mid + 1;<br>
size = size - half - 1;<br>
} else {<br>
size = half;<br>
}<br>
}<br>
return first;<br>
}</p>
<p>int main(){<br>
#ifdef debug<br>
freopen(&quot;in.txt&quot;, &quot;r&quot;, stdin);<br>
int START = clock();<br>
#endif<br>
cin.tie(0);<br>
cin.sync_with_stdio(false);</p>
<pre><code>dfs(0LL);
sort(L,L+pos);
/*
for(int i=0;i&lt;pos;i++)
    cout &lt;&lt; i &lt;&lt; &quot; &quot; &lt;&lt; L[i]&lt;&lt; endl;
*/

int T;
cin &gt;&gt; T;
while(T--){
    int l,r;
    cin &gt;&gt; l &gt;&gt; r;
    LL pos1 = lower_bound(L,pos,l);
    LL pos2 = lower_bound(L,pos,r);

    LL ans1 = (L[pos1]-l+1)*L[pos1];//��һ����
    LL ans2 = 0;
    for(int i=pos1;i&lt;pos2;i++)
        ans2 += (L[i+1] - L[i])*L[i+1];
    LL ans3 = (r-L[pos2])*L[pos2];
    //cout &lt;&lt;pos1&lt;&lt;&quot; &quot;&lt;&lt;pos2&lt;&lt;endl;
    //cout &lt;&lt; ans1 &lt;&lt; &quot; &quot; &lt;&lt; ans2 &lt;&lt; &quot; &quot; &lt;&lt; ans3 &lt;&lt; endl;
    cout &lt;&lt; ans1+ans2+ans3 &lt;&lt; endl;
}

#ifdef debug
printf(&quot;Time:%.3fs.\n&quot;, double(clock() - START) / CLOCKS_PER_SEC);
#endif
return 0;
</code></pre>
<p>}</p>
<pre style="background-color:#fff">&lt;/div&gt;</pre>

AOJ 840.下一个幸运数