ABC400E
YHC_juruo
·
·
题解
ABC400E
1.翻译：
给出n次询问，每次询问给出一个数A，要找出小于等于A的最大的数字，满足此数字正好有两个不同的质因数且每个质因数都只能将它整除偶数次。
2.思路：
显然N是一个平方数。
由于我们只需要找最多10^6个平方数，所以我们可以检查每一个平方数是否符合要求。
显然k的质因数集合与k^2的质因数集合相同，所以只需计算k=1、2……10^6的不同质因数个数即可枚举出所有符合要求的数。
具体来说，初始化一个数组$V=(V1,V2……V10^6)$为$0$，对于每个不大于$10^6$的质数$p$，如果$i$是$p$的倍数，将$Vi$加$1$。那么最终的$Vi$就是$i$的不同质因数个数。
最后对找到的数组sort再二分查找一下就行了。
## 3.代码：
```cpp
#include <bits/stdc++.h>
#define int long long
#define maxn 2000005
using namespace std;
int v1[maxn],v2[maxn],cnt,answ[maxn],cnta;
signed main() {
for(int i=2;i<maxn;i++) {
if(v1[i]==0){
for(int j=i;j<maxn;j+=i) {
v1[j]++;
}
}
}
for(int i=2;i<maxn;i++){
if(v1[i]==2){
v2[++cnt]=i*i;
}
}
sort(v2+1,v2+cnt+1);
int q;
cin>>q;
while(q--){
int a;
cin>>a;
int ans=upper_bound(v2+1,v2+cnt+1,a)-v2-1;
answ[++cnta]=v2[ans];
}
for(int i=1;i<=cnta;i++){
cout<<answ[i]<<"\n";
}
return 0;
}
```