Newcoder70B.幸运数字Ⅱ（水~）

Description

定义一个数字为幸运数字当且仅当它的所有数位都是$4$4或者$7$7。

比如说，$47、744、4$47、744、4都是幸运数字而$5、17、467$5、17、467都不是。

定义$next(x)$next(x)为大于等于$x$x的第一个幸运数字。给定$l,r$l,r，请求出$\sum\limits_{i=l}^rnext(i)$i=l∑r​next(i)。

Input

两个整数$l$l和$r$r$ (1\le l\le r \le 10^9)​$

Output

一个数字表示答案。

Sample Input

2 7

Sample Output

33

Solution

找到所有的幸运数字分段计算即可

Code

#include
#include
using namespace std;
typedef long long ll;
const int maxn=100001;
ll f[maxn];
ll Solve(int n)
{
ll ans=0;
for(int i=1;;i++)
{
ans+=(min(f[i],(ll)n)-f[i-1])*f[i];
if(f[i]>=n)return ans;
}
}
int main()
{
f[1]=4,f[2]=7;
int pre=1;
for(int i=3;;)
{
int k=i-1;
for(int j=pre;j<=k;j++)f[i++]=f[j]*10+4;
for(int j=pre;j<=k;j++)f[i++]=f[j]*10+7;
if(f[i-1]>1e9)
{
sort(f+1,f+i);
break;
}
pre=k+1;
}
int l,r;
while(~scanf("%d%d",&l,&r))printf("%lld\n",Solve(r)-Solve(l-1));
return 0;
}