← Home
For problem statement at 0-999/0-99/50-59/55/problemD.txt this is a correct solution, but verifier at 0-999/0-99/50-59/55/verifierD.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var memo [20][2520][48]int64
var lcmMap [2521]int

func gcd(a, b int) int {
	for b != 0 {
		a, b = b, a%b
	}
	return a
}

func count(s string, pos int, rem int, l int, isLimit bool) int64 {
	remDigits := len(s) - pos
	if remDigits == 0 {
		if rem%l == 0 {
			return 1
		}
		return 0
	}

	if !isLimit && memo[remDigits][rem][lcmMap[l]] != -1 {
		return memo[remDigits][rem][lcmMap[l]]
	}

	var res int64 = 0
	limit := 9
	if isLimit {
		limit = int(s[pos] - '0')
	}

	for d := 0; d <= limit; d++ {
		nextRem := (rem*10 + d) % 2520
		nextLcm := l
		if d > 0 {
			nextLcm = l / gcd(l, d) * d
		}
		res += count(s, pos+1, nextRem, nextLcm, isLimit && d == limit)
	}

	if !isLimit {
		memo[remDigits][rem][lcmMap[l]] = res
	}

	return res
}

func solveNum(n int64) int64 {
	if n == 0 {
		return 0
	}
	s := strconv.FormatInt(n, 10)
	return count(s, 0, 0, 1, true)
}

func main() {
	id := 0
	for i := 1; i <= 2520; i++ {
		if 2520%i == 0 {
			lcmMap[i] = id
			id++
		}
	}

	for i := 0; i < 20; i++ {
		for j := 0; j < 2520; j++ {
			for k := 0; k < 48; k++ {
				memo[i][j][k] = -1
			}
		}
	}

	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)

	if !scanner.Scan() {
		return
	}
	t, _ := strconv.Atoi(scanner.Text())

	for i := 0; i < t; i++ {
		scanner.Scan()
		l, _ := strconv.ParseInt(scanner.Text(), 10, 64)
		scanner.Scan()
		r, _ := strconv.ParseInt(scanner.Text(), 10, 64)
		fmt.Println(solveNum(r) - solveNum(l-1))
	}
}