简单的整数相减题目的解法

给定 n 个整数，每次可以进行如下操作：选择其中最大的整数 a 与最小的整数 b，并将它们都替换为 (a−b)。

是否可以在有限次操作内使得所有整数都相等？如果是，最后的结果是什么？

有多组测试数据。第一行输入一个整数 T（约 20）代表测试数据组数。对于每组测试数据：

第一行输入一个整数 n（2≤n≤10）代表给定整数的数量。

第二行输入 n 个整数 a​1​​,a​2​​,⋯,a​n​​（−10​5​​≤a​i​​≤10​5​​）代表给定的整数。

每组数据输出一行。若可以将所有整数变为相等，输出最终产生的那个整数；否则输出 "Impossible"（不输出引号）。
Sample Input / 样例输入

2
3
1 2 3
2
5 5


Sample Output / 样例输出

2
5













package main

import (
        "bufio"
        "container/heap"
        "fmt"
        "os"
        "strconv"
        "strings"
)

// An IntHeap is a min-heap of ints.
type MinIntHeap []*Item

func (h MinIntHeap) Len() int           { return len(h) }
func (h MinIntHeap) Less(i, j int) bool { return h[i].value < h[j].value }
func (h MinIntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i]; h[i].IndexMin, h[j].IndexMin = i, j }

func (h *MinIntHeap) Push(x interface{}) {
        // Push and Pop use pointer receivers because they modify the slice's length,
        // not just its contents.
        item := x.(*Item)
        item.IndexMin = len(*h)
        *h = append(*h, item)
}

func (h *MinIntHeap) Pop() interface{} {
        old := *h
        n := len(old)
        x := old[n-1]
        *h = old[0 : n-1]
        return x
}

type Item struct {
        value    int
        IndexMax int
        IndexMin int
}

// An IntHeap is a min-heap of ints.
type MaxIntHeap []*Item

func (h MaxIntHeap) Len() int           { return len(h) }
func (h MaxIntHeap) Less(i, j int) bool { return h[i].value > h[j].value }
func (h MaxIntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i]; h[i].IndexMax, h[j].IndexMax = i, j }

func (h *MaxIntHeap) Push(x interface{}) {
        // Push and Pop use pointer receivers because they modify the slice's length,
        // not just its contents.
        item := x.(*Item)
        item.IndexMax = len(*h)
        *h = append(*h, item)
}

func (h *MaxIntHeap) Pop() interface{} {
        old := *h
        n := len(old)
        x := old[n-1]
        *h = old[0 : n-1]
        return x
}

// This example inserts several ints into an IntHeap, checks the minimum,
// and removes them in order of priority.
func main() {
        reader := bufio.NewReader(os.Stdin)
        text, _ := reader.ReadString('\n')
        text = strings.TrimSpace(text)
        num, _ := strconv.Atoi(text)

        for i := 0; i < num; i++ {
                reader.ReadString('\n')
                str, _ := reader.ReadString('\n')
                str = strings.TrimSpace(str)

                hmin := &MinIntHeap{}
                heap.Init(hmin)

                hmax := &MaxIntHeap{}
                heap.Init(hmax)

                for _, s := range strings.Split(str, " ") {
                        n, _ := strconv.Atoi(s)
                        item := &Item{}
                        item.value = n
                        heap.Push(hmin, item)
                        heap.Push(hmax, item)
                }

                for {
                        max := heap.Pop(hmax).(*Item)
                        min := heap.Pop(hmin).(*Item)
                        if max.value == min.value {
                                fmt.Println(strconv.Itoa(min.value))
                                break
                        }
                        newvalue := max.value - min.value
                        max.value = newvalue
                        min.value = newvalue
                        heap.Push(hmax, max)
                        heap.Fix(hmax, min.IndexMax)
                        heap.Fix(hmin, max.IndexMin)
                        heap.Push(hmin, min)
                }
        }
}