求和

用 f(x)f(x) 来表示满足下列条件的最小正整数 aa:

  1. a≥xa≥x。
  2. aa 的各个数位不包含除了 44 和 77 以外的其他数字。

现在,给定两个整数 l,r(l≤r)l,r(l≤r),请你计算 f(l)+f(l+1)+…+f(r)f(l)+f(l+1)+…+f(r) 的值。

输入格式

一行,两个整数 l,rl,r。

输出格式

一行,一个整数表示求得的和。

用 f(x)来表示满足下列条件的最小正整数 aa:

  1. a≥x
  2. a 的各个数位不包含除了 4 和 7 以外的其他数字。

现在,给定两个整数 l,r(l≤r)l,r(l≤r),请你计算 f(l)+f(l+1)+…+f(r)f(l)+f(l+1)+…+f(r) 的值。

数据范围

前三个测试点满足 1≤l≤r≤10
所有测试点满足 1≤l≤r≤10^9

输入样例1:

2 7

输出样例1:

33

输入样例2:

7 7

输出样例2:

7
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;

vector<LL> S;

void dfs(int u,LL x){  //此时数字位数为u,结果为x
    S.push_back(x);
    if(u==10)return ;
    dfs(u+1,x*10+4);
    dfs(u+1,x*10+7);
}
int main()
{
   // S.push_back(0);
    dfs(0,0);
    sort(S.begin(),S.end());
    LL l,r;
    cin>>l>>r;
    LL ans=0;
    for(int i=1;i<(int)S.size();i++)
    {
       LL a=S[i-1]+1,b=S[i];
     //  cout<<a<<' '<<b<<endl;
       if(r<a)break;
       if(b<l)continue;
       ans+=(min(b,r)-max(a,l)+1)*S[i];
       
    }
    cout<<ans;
    return 0;
}

 

 
上一篇:p010_sort_list_simple


下一篇:Educational Codeforces Round 5 部分题解