Luogu P8054 A 质因数 题解

题目描述

定义 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)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;
}