Submission #164665

---

Source Code Expand

#include <iostream>
#include <sstream>
#include <cstdlib>
using namespace std;

typedef long long ll;

ll p[20], f[20];

ll func(const string& s, int k)
{
    if (k>=s.size()) return 0;
    ll res=0;
    for(int i=0;i<s[k]-'0';++i) {
        if (i==4 or i==9)
            res+=p[s.size()-k-1];
        else
            res+=f[s.size()-k-1];
    }
    if (s[k]=='4' or s[k]=='9') {
        string t=s.substr(k+1);
        res+=strtoll(t.c_str(), 0, 10)+1;
        return res;
    }
    res+=func(s, k+1);
    return res;
}
ll func(ll x)
{
    if (x<10) return (x>=4)+(x>=9);

    ostringstream os; os<<x;
    string s=os.str();
    return func(s, 0);
}

int main()
{
    p[0]=1; f[0]=0;
    for(int i=1;i<20;++i) {
        p[i]=10*p[i-1];
        f[i]=2*p[i-1]+8*f[i-1];
    }

    ll a, b; cin>>a>>b;
    cout<<func(b)-func(a-1)<<endl;
}

Submission Info

Judge Result