GFG Code India Code

#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 dp[20][2][2][2][2][2][2][3][5][7][2][3][2];
ll recursion(int pos,int small,int two,int three,int five,int seven,int mod2,int mod3,int mod5,int mod7, int zero , int sumg1 ,int start ,string &curr)
{
   if(pos==curr.size())
   {
      if(start==1)
            return 0ll;
      if(zero==1)
            return sumg1==2;
      if(two==1 && mod2==0)
            return 1ll;
      if(three==1 && mod3==0)
            return 1ll;
      if(five==1 && mod5==0)
            return 1ll;
      if(seven==1 && mod7==0)
            return 1ll;
      return 0ll;
   }

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

   if(start==1)
         val=recursion(pos+1,1,two,three,five,seven,mod2,mod3,mod5,mod7,zero,sumg1,1,curr);

   for(int i=start;i<=9;i++)
   {
      int n2=two;
      int n3=three;
      int n5=five;
      int n7=seven;
      int n0=zero;

      if(i==0)
            n0=1;
      if(i%2==0 && i!=0)
            n2=1;
      if(i%3==0 && i!=0)
            n3=1;
      if(i%5==0 && i!=0)
            n5=1;
      if(i%7==0 && i!=0)
            n7=1;

      int k=i*i*i*i;
      int nsumg1=sumg1;

      if(k>1)
            nsumg1=2;
      else if(nsumg1!=2 && k==1)
            nsumg1++;

      if(small==1 || i<curr[pos]-'0')
            val+=recursion(pos+1,1,n2,n3,n5,n7,(mod2+k)%2,(mod3+k)%3,(mod5+k)%5,(mod7+k)%7,n0,nsumg1,0,curr);
      else if(i==curr[pos]-'0')
            val+=recursion(pos+1,0,n2,n3,n5,n7,(mod2+k)%2,(mod3+k)%3,(mod5+k)%5,(mod7+k)%7,n0,nsumg1,0,curr);
   }
   return val;
}

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

   int t;
   cin >> t;
   while(t--)
   {
      string s;
      cin >> s;

      memset(dp,-1,sizeof(dp));
      ll ans=recursion(0,0,0,0,0,0,0,0,0,0,0,0,1,s);
      cout << ans << "\n";
   }
}