自动搬运

查看原文

来自洛谷，原作者为

	lihanwen12 **

搬运于2025-08-24 22:35:33，当前版本为作者最后更新于2022-01-24 23:31:24，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

萌新的第一篇题解！
题目大意：我们想要找到一个数字 $m$ 使得 $m<n$ 且 $f(m)>f(n)$，$f(x)$ 表示 $x$ 分解质因数后得到的质数个数。
显然令 $m=2^k$ 最有可能满足条件，因为这样 $m$ 较小且分解质因数后的质数个数更多。
举个例子：
$n=60=2\times2\times3\times5,f(n)=4$。
$m=32=2\times2\times2\times2\times2,f(m)=5$。
将 $n$ 不停地除以 $2$ 直到不能整除为止，观察剩余部分（注意 $n$ 可能是 $2$ 的正整数次幂）：
如果 $n=2^{a_1}\times3$，令 $m=2^{a_1+1},m<n,f(m)=f(n)$ 输出 $0$。
如果 $n=2^{a_1}\times5$，令 $m=2^{a_1+2},m<n,f(m)=f(n)+1$ 输出 $1$。
如果 $n=2^{a_1}\times7$，令 $m=2^{a_1+2},m<n,f(m)=f(n)+1$ 输出 $1$。
$\cdots$
除了 $1$ 和质数 $3$ 无法满足，其他大于 $3$ 的质数 $P_i$ 都满足 $P_i>2\times2$，即 $m$ 存在。
代码如下：

#include<bits/stdc++.h>
using namespace std;
long long T,n;
int main(){
	cin>>T;
	while(T--){
		cin>>n;
		while(n%2==0){
			n=n/2;
		}
		if(n==1 || n==3)//n=1表示输入的n是2的整数次幂
			cout<<0<<endl;
		else
			cout<<1<<endl;
	}
	return 0;
}