← Home
For problem statement at 0-999/0-99/90-99/93/problemE.txt this is a correct solution, but verifier at 0-999/0-99/90-99/93/verifierE.go ends with All tests passed can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"io"
	"math"
	"os"
)

func main() {
	data, _ := io.ReadAll(os.Stdin)
	idx := 0
	readInt64 := func() int64 {
		for idx < len(data) && (data[idx] < '0' || data[idx] > '9') {
			idx++
		}
		var v int64
		for idx < len(data) && data[idx] >= '0' && data[idx] <= '9' {
			v = v*10 + int64(data[idx]-'0')
			idx++
		}
		return v
	}

	n := readInt64()
	k := int(readInt64())

	a := make([]int, 0, k)
	for i := 0; i < k; i++ {
		x := int(readInt64())
		if x == 1 {
			w := bufio.NewWriterSize(os.Stdout, 32)
			fmt.Fprint(w, 0)
			w.Flush()
			return
		}
		if int64(x) <= n {
			a = append(a, x)
		}
	}

	if len(a) == 0 {
		w := bufio.NewWriterSize(os.Stdout, 32)
		fmt.Fprint(w, n)
		w.Flush()
		return
	}

	m := int(math.Sqrt(float64(n)))
	for int64(m+1)*int64(m+1) <= n {
		m++
	}
	for int64(m)*int64(m) > n {
		m--
	}

	small := make([]int64, m+1)
	large := make([]int64, m+1)

	for i := 1; i <= m; i++ {
		small[i] = int64(i)
		large[i] = n / int64(i)
	}

	s := small
	l := large

	for _, v := range a {
		lim := m / v

		for i, j := 1, v; i <= lim; i, j = i+1, j+v {
			l[i] -= l[j]
		}

		c := n / int64(v)
		i := lim + 1
		for i <= m {
			y := int(c / int64(i))
			if y == 0 {
				break
			}
			r := int(c / int64(y))
			if r > m {
				r = m
			}
			val := s[y]
			for ; i <= r; i++ {
				l[i] -= val
			}
		}

		if v <= m {
			q := m / v
			threshold := q * v
			val := s[q]
			for x := m; x >= v; x-- {
				if x < threshold {
					q--
					threshold -= v
					val = s[q]
				}
				s[x] -= val
			}
		}
	}

	w := bufio.NewWriterSize(os.Stdout, 32)
	fmt.Fprint(w, l[1])
	w.Flush()
}