自动搬运

查看原文

来自洛谷，原作者为

	Eason_cyx Play like you never did before?

搬运于2025-08-24 23:09:55，当前版本为作者最后更新于2024-08-04 15:12:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

签到题。

先看 1 询问：

分析一次操作，例如 $2310$ 和 $1890$ 进行操作。将两个数分解质因数得到，$2310=2\times3\times5\times7\times11$，$1890=2\times3\times5\times7\times3\times3$。操作完毕得到的数为 $210=2\times3\times5\times7$。可以看出，一次操作之后会将 $x$ 的质因子至少删去一个。当所有因子只剩下一个时，不能再删了，即为不能操作。

那么为了尽可能多地操作，我们只需要保证一次删去一个质因子即可，那么记初始 $x$ 的质因子个数为 $n$（例：$2310=2\times3\times5\times7\times11$，所以 $n=5$），那么最大操作次数显然是 $n-1$。

于是我们直接 $\Theta(\sqrt n)$ 枚举出 $x$ 的质因子个数即可。

再看 2 询问：

给定 $q$，求出一个最小的 $x$，使得 $x$ 最多能进行恰好 $q$ 次操作。

那么既然能进行 $q$ 次操作，如果我们按最优方式操作，这个数一定只有 $q+1$ 个质因子。为了让这个 $x$ 最小，那么所有质因子也应该尽可能小。我们知道最小的质数为 $2$，所以这个询问的答案就是 $2^{q+1}$。$\Theta(q)$ 计算即可。

最终的时间复杂度为 $\Theta(T\sqrt{n})$，可以通过本题。记得开 unsigned long long。

#include <bits/stdc++.h>
using namespace std;
bool isp(int x) {
	if(x <= 1) return false;
	for(int i = 2;i * i <= x;i++) {
		if(x % i == 0) return false;
	}
	return true;
}
int main() {
	int t; cin >> t;
	while(t--) {
		int opt,x; cin >> opt >> x;
		if(opt == 1) {
			int cnt = 0;
			for(int i = 2;i * i <= x;i++) {
				if(x % i == 0 && isp(i)) {
					while(x % i == 0) {cnt++; x /= i;}
					if(x == 1) {cnt--; break;}
				}
			}
			cout << cnt << endl;
		}
		else {
			unsigned long long p = 1;
			for(int i = 1;i <= x+1;i++) p *= 2;
			cout << p << endl;
		}
	}
	return 0;
}