ABC-276解题报告

发表于 分类于

D. Divide by 2 or 3

题意：给你一个数组 aa，每次可以选择一个 22 的倍数除以 22，或选择一个 33 的倍数除以三。问最少多少次操作将元素统一。无解输出 -1。

如果有解，结果将会是 aa 中元素的公因数，而所有公因数都是最大公因数的因数。由于额外的除法没有意义，最终结果一定是最大公因数。对于每个元素检查它与最大公因数是否只差了若干个 22 和若干个 33。对 aigcd⁡\frac{a_i}{\gcd} 进行类似质因数分解的操作即可。

By zhoukangyang

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<bits/stdc++.h>
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define me(a, x) memset(a, x, sizeof(a))
#define ull unsigned long long
#define ld __float128
#define i128 __int128
using namespace std;
const int N = 1e6 + 7, mod = 998244353;
int n, m, a[N];
int main() {
//	freopen("thewitness.in", "r", stdin);
//	freopen("thewitness.out", "w", stdout);
    ios :: sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n ;
    int g = 0;
    L(i, 1, n) cin >> a[i], g = __gcd(a[i], g);

    int ns = 0;
    L(i, 1, n) {
        a[i] /= g;
        while(a[i] % 2 == 0) ++ns, a[i] /= 2;
        while(a[i] % 3 == 0) ++ns, a[i] /= 3;
        if(a[i] > 1) {
            cout << -1 << '\n';
            return 0;
        }
    }
    cout << ns << '\n';
    return 0;
}