题解 | #红与黑#

K题题解

这题需要了解前置知识gcd，及最大公因数求法

对于任意两个位于同一数组中的数$a_i,a_{j}a\_i,a\_j$，我们可以通过不断进行减法操作将其变成$gcd(a_i,a_j)gcd(a\_i,a\_j)$，对一个数组中所有的数进行该操作可以将整个数组变成$n-1n-1$个$00$和一个等于原数组gcd的整数，而这种操作的逆操作可以使得由一个整数$xx$和$n-1n-1$个$00$组成的数组变成一个gcd为$xx$的数组

那么我们求出数组a与数组b的gcd，当两者的gcd相等时，数组a可以通过一系列操作变成数组b

AC代码https://ac.nowcoder.com/acm/contest/view-submission?submissionId=60101895