用 f(x)f(x) 来表示满足下列条件的最小正整数 aa:
- a≥xa≥x。
- 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:
- a≥x
- 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; }