正经题解｜质因

题面大意

给定一个数字$x$，求解该$x$的质因子数$cnt$是否满足$cnt > \lfloor \frac{2}{x} \rfloor$ 的条件。

思路解析

根据打表可得，在$x = 3、5、7$时，才可能满足条件$cnt > \lfloor \frac{2}{x} \rfloor$,其余都不满足.

因此可使用简单的判断语句x == 3 || x == 5 || x == 7 ? YES : NO从而在$O(1)$的时间复杂度求解。

PS:留意$x$的取值最大为$10^{18}$

时间复杂度

$O(1)$

代码示范

#include<bits/stdc++.h>
using namespace std;

void solve()
{
	long long x;
	cin >> x;
	if(x == 3 || x == 5 || x == 7){
		cout << "YES" << endl;
		return ;
	}
	cout << "NO" << endl;
}

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		solve();
	}
	return 0;
}