题目描述

定义 $f(x)$ 表示 $x$ 分解质因数后得到的质数个数
给定一个数 $n$，求是否存在一个数 $m (1 < m < n)$，使得 $f(m) > f(n)$。

解题思路

先看一下数据范围，$1\leq T\leq 10^4$，$2\leq n\leq 10^{18}$，暴力肯定 TLE，我们需要考虑一种复杂度较低的算法。

根据小学学过的知识可知，分解质因数得到的数字一定是质数，我们可以枚举一部分数字的答案，找找其中的规律。

算出答案后，我们去除 $1$ 的情况，只考虑为 $f(m) > f(n)$ 为 false 的情况，得到一个数列，观察数列发现只有 $x$ 格式为 $2^n$ 或者 $3 \times 2^n$ 时 $f(m) > f(n)$ 才不成立，得到结论后，这道题就很简单了。

注意要开 long long ！！！

程序实现

如何判断 $x$ 格式为 $2^n$ 或者 $3 \times 2^n$ 呢？我们可以使用 cmath 自带的 log2() 函数，如果 $\log2(x)$ 后是整数，那它的格式一定是 $2^n$。如果 $\log2(\dfrac{x}{3})$ 后是整数，那它的格式一定是 $3 \times 2^n$。

#include <iostream>
#include <cmath> // log2() 函数需要的头文件

typedef long long ll; // 不开 long long 见祖宗！

int main()
{
    long long t, n;
    std::cin >> t;
    while (t--)
    {
        std::cin >> n;
        double x1 = log2(n);
        double x2 = log2(n / 3.0); // 注意处理精度问题！
        if (x1 == (ll)x1 || x2 == (ll)x2)
            puts("0");
        else
            puts("1");
    }
    return 0;
}