题解 | 不包含本位置值的累乘数组

package main

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

func main() {
	for {
		scanner := bufio.NewScanner(os.Stdin)

		// 设置大缓冲区，防止大输入时出错
		buf := make([]byte, 1024*1024) // 1MB
		scanner.Buffer(buf, 1024*1024)
		scanner.Split(bufio.ScanWords) // 按单词扫描（空格、换行等分隔）

		// 读取第一行：n
		scanner.Scan()
		n, _ := strconv.Atoi(scanner.Text())
		if n == 0 {
			break
		}
		scanner.Scan()
		k, _ := strconv.Atoi(scanner.Text())

		arr := make([]int, n)
		for i := 0; i < n; i++ {
			scanner.Scan()
			arr[i], _ = strconv.Atoi(scanner.Text())
		}
		process(arr, k)
		for i := 0; i < n; i++ {
			fmt.Printf("%d ", arr[i])
		}
	}
}

func process(arr []int, k int) {
	n := len(arr)
	l0, r0 := make([]int, n), make([]int, n)
	l0[0] = 1
  // 构建左边累成
	for i := 1; i < n; i++ {
		l0[i] = (l0[i-1] * arr[i-1]) % k
	}
	r0[n-1] = 1
    // 构建右边累成
	for i := n - 2; i >= 0; i-- {
		r0[i] = (r0[i+1] * arr[i+1]) % k
	}

	for i := 0; i < n; i++ {
		arr[i] = (l0[i] * r0[i]) % k
	}
}