题目内容

给定一个 pair $(a,b)$，定义其满意度为 $|a-b|$。为了让满意度最小，你可以选择不操作，或将 $(a,b)$ 变成 $(a, b-a)$ 或 $(b, a-b)$。 现有 $n$ 个 pair，请你进行一些操作，令操作后的 $n$ 个 pair 的满意度之和最小，且达成该最小满意度之和的操作次数最少。

思路

  此题其实隐含一个数学知识点，那就是最大公约数，如题中这种对两个数进行操作的方法其实就是辗转相减法求最大公约数的方法，对两个数如此操作下去最后必然两个数都会变成他们之间最大公约数，所以n个pair操作到最后最小满意度一定是0，所以可以模拟操作过程来计算两个数需要多少步才能均变成最大公约数，注意这个过程可以加速

代码

c++

#include <iostream>

int main() {
    int q;