526互联

Codeforces Round 653 (Div. 3) B. Multiply by 2, divide by 6

发布时间 2023-10-16 00:12:41作者: zsxuan

给一个正整数 \(n\) ，每一步可以让 \(n\) 除以 \(6\) 或者让 \(n\) 乘以 \(2\) 。询问进过多少次操作可以使得 \(n\) 变为 \(1\) 。或者回答不可能。

在唯一分解定理下观察 \(n\) 。

  • 如果 \(n\) 除以 \(6\) ，则 \(2^{\alpha_1}3^{\alpha_2-1}\) 会变为 \(2^{\alpha_1-1}3^{\alpha_2-1}\) 。
  • 如果 \(n\) 乘以 \(2\) ，则 \(2^{\alpha_1}\) 会变成 \(2^{\alpha_1+1}\) 。

于是若 \(n\) 存在 \(2, 3\) 以外的质因子则不能变为 \(1\) 。

若 \(\alpha_1 > \alpha_2\) 则不能变为 \(1\) 。

否则 \(n\) 能变为 \(1\) ，操作次数为 \(\alpha_2 + (\alpha_2 - \alpha_1)\)。

view 
#include <bits/stdc++.h>
typedef long long ll;
void solve(){
	int n; std::cin >> n;
	int cnt2 = 0, cnt3 = 0;
	while (n % 2 == 0) {
		cnt2 += 1;
		n /= 2;
	}
	while (n % 3 == 0) {
		cnt3 += 1;
		n /= 3;
	}
	if (n > 1) std::cout << -1 << '\n';
	else if (cnt2 > cnt3) std::cout << -1 << '\n';
	else std::cout << cnt3 + (cnt3 - cnt2) << '\n';
}
int main() {
	int _ = 1; std::cin >> _;
	while (_--) {solve();}
	return 0;
}