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)
}