[Spoj] GONE - G One Number

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : GONE - G One Number
Source            : Spoj
Category          : Dynamic Programing
Algorithm         : Digit DP
Verdict           : Accepted
Type - 2

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll       long long
 
template <typename T> string toString(T num) { stringstream iss; iss << num; return iss.str(); }
 
bool isprime[100 + 5];
 
inline bool checkPrime(int num)
{
      if (num <= 1) return 0;
      if (num <= 3) return 1;
      if (~num & 1) return 0;
      for (int i = 3; i*i <= num; i += 2) if (num % i == 0) return 0;
      return 1;
}
 
inline void smallSeive()
{
      for (int i = 1; i <= 100; i++) isprime[i] = checkPrime(i);
}
 
ll dp[12][4][100 + 5];
bool memoize[12][4][100 + 5];
 
string A, B;
int K;
 
inline ll compute(int sumDigit)
{
      return isprime[sumDigit];
}
 
inline ll solve(string &a, int limit, int indx = 0, int small = 1, int sumdigit = 0)
{
      if (indx == limit - 1 && small == 2) return 0;
      if (indx >= limit) return 0;
      ll &ret = dp[indx][small][sumdigit];
      bool &mem = memoize[indx][small][sumdigit];
      if (mem) return ret;
      mem = 1;
      int loop = 9;
      int i = 0;
      if (indx == 0) i = 1;
      int num = a[indx] - '0';
      ll sum = 0;
      for ( ; i <= loop; i++)
      {
            if (small == 0)
            {
                  sum += compute(sumdigit + i) + solve(a, limit, indx+1, 0, sumdigit + i);
            }
            if (small == 2)
            {
                  sum += compute(sumdigit + i) + solve(a, limit, indx+1, 2, sumdigit + i);
            }
            if (small == 1)
            {
                  if (i > num && indx != limit-1)
                  {
                        sum += compute(sumdigit + i) + solve(a, limit, indx+1, 2, sumdigit + i);
                  }
                  if (i < num)
                  {
                        sum += compute(sumdigit + i) + solve(a, limit, indx+1, 0, sumdigit + i);
                  }
                  if (i == num)
                  {
                        sum += compute(sumdigit + i) + solve(a, limit, indx+1, 1, sumdigit + i);
                  }
            }
      }
      return ret = sum;
}
 
int main()
{
      smallSeive();
      int tc;
      cin >> tc;
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            ll num1, num2;
            cin >> num1 >> num2;
            if (num1 > num2) swap(num1, num2);
            A = toString(num1-1);
            B = toString(num2);
            ll sum1 = 0, sum2 = 0;
            memset(memoize, 0, sizeof memoize);
            sum1 = solve(A, A.size());
            memset(memoize, 0, sizeof memoize);
            sum2 = solve(B, B.size());
            ll sum = sum2 - sum1;
            cout << sum << endl;
      }
}