Number of ways

Sequence gcd

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>

int calculate_gcd(int a, int b) {
    if (a == 0) return b;
    if (b == 0) return a;
    return std::gcd(a, b);
}

long long dp[20][2][2][10][2];
bool visited[20][2][2][10][2];

std::string S;

long long solve(int idx, bool tight, bool is_leading_zero, int current_gcd_val, bool has_zero_digit) {
    if (idx == S.length()) {
        if (is_leading_zero) {
            return 0;
        }
        if (has_zero_digit) {
            return 0;
        }
        return current_gcd_val;
    }

    if (visited[idx][tight][is_leading_zero][current_gcd_val][has_zero_digit]) {
        return dp[idx][tight][is_leading_zero][current_gcd_val][has_zero_digit];
    }

    long long ans = 0;
    int upper_bound = tight ? (S[idx] - '0') : 9;

    for (int digit = 0; digit <= upper_bound; ++digit) {
        bool new_tight = tight && (digit == upper_bound);
        bool new_is_leading_zero = is_leading_zero && (digit == 0);
        bool new_has_zero_digit = has_zero_digit || (!is_leading_zero && digit == 0);

        int next_gcd_for_param;
        if (new_is_leading_zero) {
            next_gcd_for_param = 0;
        } else {
            if (digit != 0) {
                if (current_gcd_val == 0) {
                    next_gcd_for_param = digit;
                } else {
                    next_gcd_for_param = calculate_gcd(current_gcd_val, digit);
                }
            } else {
                next_gcd_for_param = current_gcd_val;
            }
        }
        
        ans += solve(idx + 1, new_tight, new_is_leading_zero, next_gcd_for_param, new_has_zero_digit);
    }

    visited[idx][tight][is_leading_zero][current_gcd_val][has_zero_digit] = true;
    return dp[idx][tight][is_leading_zero][current_gcd_val][has_zero_digit] = ans;
}

long long solve_up_to(long long N_val) {
    if (N_val == 0) {
        return 0;
    }
    S = std::to_string(N_val);
    
    for (int i = 0; i < 20; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                for (int l = 0; l < 10; ++l) {
                    for (int m = 0; m < 2; ++m) {
                        visited[i][j][k][l][m] = false;
                        dp[i][j][k][l][m] = 0;
                    }
                }
            }
        }
    }
    return solve(0, true, true, 0, false);
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int T;
    std::cin >> T;

    while (T--) {
        long long L, R;
        std::cin >> L >> R;

        long long ans_R = solve_up_to(R);
        long long ans_L_minus_1 = solve_up_to(L - 1);

        long long final_answer = ans_R - ans_L_minus_1;
        std::cout << final_answer << std::endl;
    }

    return 0;
}