题解

题目分析

给定一个整数序列，我们可以对其中的每个数进行任意次的倍增操作，每次操作可以将选中的数乘以 2 或乘以 3。目标是判断是否能够通过这样的操作使所有数相等。

解题思路

通过倍增操作（乘以 2 或 3），我们可以改变每个数中 2 和 3 的次幂。因此，为了判断是否能够让所有数相等，我们可以将问题简化为以下步骤：

1. 去除每个数中的 2 和 3 的因子：对序列中的每个数，除去所有 2 和 3 因子，得到一个新的数。
2. 检查剩余部分是否相等：如果所有数去除 2 和 3 因子后的剩余部分相等，则可以通过倍增操作使所有数相等；否则，无法使它们相等。

数论解释

一个整数可以表示为以下形式：

其中：

• ( 2^x ) 表示数 ( a_i ) 中的因子 2 的幂次。
• ( 3^y ) 表示数 ( a_i ) 中的因子 3 的幂次。
• ( b_i ) 是去掉 2 和 3 因子后的剩余部分。

倍增操作（乘以 2 或 3）只能改变 ( 2^x ) 和 ( 3^y ) 的值，而无法影响 ( b_i )。因此，如果所有数的 ( b_i ) 不相等，那么无论如何倍增，数值都无法变得相同。 其中 ( 2^x ) 和 ( 3^y ) 是 2 和 3 的次幂，而 ( b_i ) 是去除 2 和 3 因子后的剩余部分。因为倍增操作只能影响数中的 2 和 3 的次幂，( b_i ) 的值无法通过操作改变。所以，只有当所有数的 ( b_i ) 相等时，才能通过倍增操作将它们变成相同的数。

算法步骤

1. 对每个数去除 2 和 3 因子。
2. 检查去除 2 和 3 因子后的数是否都相等。
3. 如果相等，输出 Yes；否则，输出 No。

代码实现

以下是使用 C 语言的代码实现：

#include <stdio.h>

// 去除数字 n 中的因子 factor
int remove_factors(int n, int factor) {
    while (n % factor == 0) {
        n /= factor;
    }
    return n;
}

// 判断能否通过倍增操作使得数组中所有元素相等
int can_make_equal(int arr[], int n) {
    // 第一个数去掉 2 和 3 因子后的结果
    int base_value = remove_factors(arr[0], 2);
    base_value = remove_factors(base_value, 3);

    // 检查每个数去掉 2 和 3 后是否与 base_value 相等
    for (int i = 1; i < n; i++) {
        int value = remove_factors(arr[i], 2);
        value = remove_factors(value, 3);
        if (value != base_value) {
            return 0;  // 如果有不同的数，返回 0 表示 No
        }
    }
    return 1;  // 全部相等，返回 1 表示 Yes
}

int main() {
    int n;
    scanf("%d", &n);

    int arr[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &arr[i]);
    }

    if (can_make_equal(arr, n)) {
        printf("Yes\n");
    } else {
        printf("No\n");
    }

    return 0;
}