Google Kickstart Round A Problem D

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef long long ll;
#define pb push_back
#define ff first
#define ss second
const int N=3e5+7;
const int mod=1e9+7;
const double eps=1e-6;
const double pi=    3.14159265358979323846;
using namespace std;
using namespace __gnu_pbds;
typedef tree<int, null_type, less_equal<int>, rb_tree_tag,
             tree_order_statistics_node_update>
    op_set;

ll binpow(ll base, ll ex)
{
    ll ans=1;
    while(ex>0)
    {
        if(ex%2==1)
                ans=ans*base;
        base=base*base;
        ex=ex/2;
    }
    return ans;
}

ll dp[15][2][125][8][6][4][4][2][2];
ll recursion(int pos,int small,int sum,int two,int three,int five,int seven,int zero,int start,string &curr)
{
    if(pos==curr.size())
    {
        ll formed=1ll;
        formed=formed*binpow(2,two);
        formed=formed*binpow(3,three);
        formed=formed*binpow(5,five);
        formed=formed*binpow(7,seven);
        if(zero==1)
                formed=0;
        if(start==1)
            return 0ll;

        if(formed%sum==0)
                return 1ll;
        return 0ll;
    }

    ll &val=dp[pos][small][sum][two][three][five][seven][zero][start];
    if(val!=-1)
            return val;
    val=0;

    if(start==1)
            val+=recursion(pos+1,1,sum,two,three,five,seven,zero,1,curr);

    for(int i=start;i<10;i++)
    {
        int ntwo=two;
        int nthree=three;
        int nfive=five;
        int nseven=seven;
        int nzero=zero;
        int nsum=sum+i;

        if(i==0)
                nzero=1;
        else if(i==2)
                ntwo=std::min(ntwo+1,7);
        else if(i==3)
                nthree=std::min(nthree+1,5);
        else if(i==4)
                ntwo=std::min(ntwo+2,7);
        else if(i==5)
                nfive=std::min(nfive+1,3);
        else if(i==6)
        {
            nthree=std::min(nthree+1,5);
            ntwo=std::min(ntwo+1,7);
        }
        else if(i==7)
                nseven=std::min(nseven+1,3);
        else if(i==8)
                ntwo=std::min(ntwo+3,7);
        else if(i==9)
                nthree=std::min(nthree+2,5);

        if(small || i<curr[pos]-'0')
                val+=recursion(pos+1,1,nsum,ntwo,nthree,nfive,nseven,nzero,0,curr);
        else if(i==curr[pos]-'0')
                val+=recursion(pos+1,0,nsum,ntwo,nthree,nfive,nseven,nzero,0,curr);
    }
    return val;
}

int32_t main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(0);

   int tc;
   cin >> tc;
   for(int t=1;t<=tc;t++)
   {
        cout << "Case #" << t << ": ";

        ll a,b;
        cin >> a >> b;

        a--;

        string L=to_string(a);
        string R=to_string(b);

        ll ans=0;
        memset(dp,-1,sizeof(dp));
        ans+=recursion(0,0,0,0,0,0,0,0,1,R);
        memset(dp,-1,sizeof(dp));
        ans-=recursion(0,0,0,0,0,0,0,0,1,L);

        cout << ans << "\n";
   }
}