← Home
For problem statement at 0-999/500-599/540-549/542/problemD.txt this is a correct solution, but verifier at 0-999/500-599/540-549/542/verifierD.go ends with build reference failed: chdir 0-999/500-599/540-549/542: no such file or directory

exit status 1 can you fix the verifier? package main

import (
	"bufio"
	"fmt"
	"math"
	"math/big"
	"os"
	"sort"
)

type pair struct {
	tIdx int
	rIdx int
}

func sieve(limit int) []int {
	isComp := make([]bool, limit+1)
	primes := []int{}
	for i := 2; i <= limit; i++ {
		if !isComp[i] {
			primes = append(primes, i)
			if int64(i)*int64(i) <= int64(limit) {
				for j := i * i; j <= limit; j += i {
					isComp[j] = true
				}
			}
		}
	}
	return primes
}

func factorize(n uint64, primes []int) [][2]uint64 {
	res := make([][2]uint64, 0)
	rest := n
	for _, p := range primes {
		pp := uint64(p)
		if pp*pp > rest {
			break
		}
		if rest%pp == 0 {
			cnt := uint64(0)
			for rest%pp == 0 {
				rest /= pp
				cnt++
			}
			res = append(res, [2]uint64{pp, cnt})
		}
	}
	if rest > 1 {
		res = append(res, [2]uint64{rest, 1})
	}
	return res
}

func genDivisors(facs [][2]uint64) []uint64 {
	divs := []uint64{1}
	for _, fe := range facs {
		p, e := fe[0], fe[1]
		sz := len(divs)
		mul := uint64(1)
		for i := uint64(1); i <= e; i++ {
			mul *= p
			for j := 0; j < sz; j++ {
				divs = append(divs, divs[j]*mul)
			}
		}
	}
	return divs
}

func isPrimeBig(n uint64) bool {
	if n < 2 {
		return false
	}
	small := []uint64{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}
	for _, p := range small {
		if n%p == 0 {
			return n == p
		}
	}
	d := new(big.Int).SetUint64(n - 1)
	s := 0
	zero := big.NewInt(0)
	one := big.NewInt(1)
	for new(big.Int).And(d, one).Cmp(zero) == 0 {
		d.Rsh(d, 1)
		s++
	}
	nBig := new(big.Int).SetUint64(n)
	bases := []uint64{2, 3, 5, 7, 11, 13, 17}
	for _, a := range bases {
		if a >= n {
			continue
		}
		aBig := new(big.Int).SetUint64(a)
		x := new(big.Int).Exp(aBig, d, nBig)
		if x.Cmp(one) == 0 || x.Cmp(new(big.Int).Sub(nBig, one)) == 0 {
			continue
		}
		composite := true
		for r := 1; r < s; r++ {
			x.Mul(x, x).Mod(x, nBig)
			if x.Cmp(new(big.Int).Sub(nBig, one)) == 0 {
				composite = false
				break
			}
		}
		if composite {
			return false
		}
	}
	return true
}

func geomSumCmp(p uint64, e int, limit uint64) int {
	term := uint64(1)
	sum := uint64(1)
	for i := 0; i < e; i++ {
		if p == 0 {
			return 1
		}
		if term > (limit-sum)/p {
			return 1
		}
		term *= p
		sum += term
		if sum > limit {
			return 1
		}
	}
	if sum < limit {
		return -1
	}
	if sum == limit {
		return 0
	}
	return 1
}

func findPForSum(total uint64, e int) (uint64, bool) {
	if e == 1 {
		p := total - 1
		if p >= 2 {
			return p, true
		}
		return 0, false
	}
	hiEst := uint64(math.Pow(float64(total), 1.0/float64(e))) + 3
	if hiEst < 2 {
		hiEst = 2
	}
	if hiEst > total-1 {
		hiEst = total - 1
	}
	low := uint64(2)
	high := hiEst
	for geomSumCmp(high, e, total) < 0 && high < total-1 {
		high *= 2
		if high >= total-1 {
			high = total - 1
			break
		}
	}
	if low > high {
		return 0, false
	}
	for low <= high {
		mid := (low + high) / 2
		c := geomSumCmp(mid, e, total)
		if c == 0 {
			return mid, true
		} else if c < 0 {
			low = mid + 1
		} else {
			if mid == 0 {
				break
			}
			high = mid - 1
		}
	}
	return 0, false
}

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var A uint64
	if _, err := fmt.Fscan(in, &A); err != nil {
		fmt.Fprintln(out, 0)
		return
	}
	if A == 1 {
		fmt.Fprintln(out, 1)
		return
	}

	maxP := int(math.Sqrt(float64(A))) + 1
	primes := sieve(maxP)

	facs := factorize(A, primes)
	divs := genDivisors(facs)
	sort.Slice(divs, func(i, j int) bool { return divs[i] < divs[j] })
	val2idx := make(map[uint64]int, len(divs))
	for i, v := range divs {
		val2idx[v] = i
	}

	pow2 := make([]uint64, 65)
	pow2[0] = 1
	for i := 1; i < 65; i++ {
		pow2[i] = pow2[i-1] << 1
	}

	type void struct{}
	primeSet := make(map[uint64]void)
	candP := make([][]uint64, len(divs))

	for i, t := range divs {
		if t == 1 {
			continue
		}
		local := make(map[uint64]void)
		// e = 1
		if t >= 2 {
			p := t - 1
			if p >= 2 && isPrimeBig(p) {
				local[p] = void{}
			}
		}
		// e >= 2
		for e := 2; e < 64; e++ {
			if pow2[e+1]-1 > t {
				break
			}
			if p, ok := findPForSum(t, e); ok {
				if p >= 2 && isPrimeBig(p) {
					local[p] = void{}
				}
			}
		}
		if len(local) > 0 {
			for p := range local {
				candP[i] = append(candP[i], p)
				primeSet[p] = void{}
			}
			sort.Slice(candP[i], func(a, b int) bool { return candP[i][a] < candP[i][b] })
		}
	}

	if len(primeSet) == 0 {
		fmt.Fprintln(out, 0)
		return
	}

	uniquePrimes := make([]uint64, 0, len(primeSet))
	for p := range primeSet {
		uniquePrimes = append(uniquePrimes, p)
	}
	sort.Slice(uniquePrimes, func(i, j int) bool { return uniquePrimes[i] < uniquePrimes[j] })
	p2idx := make(map[uint64]int, len(uniquePrimes))
	for i, p := range uniquePrimes {
		p2idx[p] = i
	}

	candIdx := make([][]int, len(divs))
	for i := range candP {
		if len(candP[i]) == 0 {
			continue
		}
		for _, p := range candP[i] {
			candIdx[i] = append(candIdx[i], p2idx[p])
		}
	}

	tWithCand := []int{}
	for i := range divs {
		if len(candIdx[i]) > 0 {
			tWithCand = append(tWithCand, i)
		}
	}

	adj := make([][]pair, len(divs))
	for ri, rv := range divs {
		if rv == 1 {
			continue
		}
		for _, ti := range tWithCand {
			tv := divs[ti]
			if rv%tv == 0 {
				nv := rv / tv
				adj[ri] = append(adj[ri], pair{tIdx: ti, rIdx: val2idx[nv]})
			}
		}
	}

	type key struct {
		r  int
		lp int
	}
	memo := make(map[key]uint64)

	var dfs func(rIdx int, lastPIdx int) uint64
	dfs = func(rIdx int, lastPIdx int) uint64 {
		if divs[rIdx] == 1 {
			return 1
		}
		k := key{r: rIdx, lp: lastPIdx}
		if v, ok := memo[k]; ok {
			return v
		}
		var res uint64 = 0
		for _, pr := range adj[rIdx] {
			ti := pr.tIdx
			for _, pidx := range candIdx[ti] {
				if pidx > lastPIdx {
					res += dfs(pr.rIdx, pidx)
				}
			}
		}
		memo[k] = res
		return res
	}

	startIdx := val2idx[A]
	ans := dfs(startIdx, -1)
	fmt.Fprintln(out, ans)
}