P8054题解

· · 题解

萌新的第一篇题解！
题目大意：我们想要找到一个数字 m 使得 m<n 且 f(m)>f(n)，f(x) 表示 x 分解质因数后得到的质数个数。
显然令 m=2^k 最有可能满足条件，因为这样 m 较小且分解质因数后的质数个数更多。
举个例子：

$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;
}