美丽数 II - 正经题解

解法：我们从 $2$ 开始，枚举不超过 $\sqrt{A_i}$ 的质因子，然后判断即可。

注意一定得遍历质数，不然单次查询时间复杂度就会退化至 $O(\sqrt{A_i})$。

#include <iostream>
#include <cstdio>
#include <vector> 
#define int long long
#pragma GCC optimize(2)
using namespace std;
bool vis[100005];
vector <int> v;
void solve(){
	int n, ct = 0;
	cin >> n;
	for(int i:v){
		if(i * i > n) break;
		while(n % i == 0) n /= i, ct++;//记录下有多少个质因子
	}
	if(ct > 3) cout << "No\n";
	else if(ct == 3 && n == 1 || ct == 2 && n != 1) cout << "Yes\n";//如果n不为1就说明还有一个质因子（就是当前的n）
	else cout << "No\n";
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	vis[0] = vis[1] = 1;
	for(int i = 2; i <= 400; i++){//提前筛一遍
		if(!vis[i]){
			for(int j = i * 2; j <= 100000; j += i) vis[j] = 1;
		}
	}
	for(int i = 2; i <= 100000; i++) if(!vis[i]) v.push_back(i);
	int t;
	cin >> t;
	while(t--) solve();

	return 0;
}

时间复杂度：$O(\sqrt{A_i}\ln\ln A_i+Q\dfrac{\sqrt{A_i}}{\ln A_i})$。