资讯详情

[https://atcoder.jp/contests/abc400/tasks/abc400_e](埃氏筛法+二分）

题意：

给定\(q\)次查询，每次查询给出一个数\(n\)，求最大的小于等于\(n\)的400数

400数：只有两个质因数，质因数次方为偶

思路：

400是两个质因数的平方数

这两个质因子乘积小于等于1e6

const int M=1e6+5;
int a[M];
vector<int>vec;
void solve(){int n;cin>>n;cout<<*prev(upper_bound(vec.begin(),vec.end(),n))<<endl;
}signed main()
{ios::sync_with_stdio(false),cin.tie(0);int T=1;
cin>>T;
for(int i=2;i<=1e6;i++){if(a[i]==0){for(int j=i;j<=1e6;j+=i)a[j]++;}
}
for(int i=1;i<=1e6;i++){if(a[i]==2){vec.pb(i*i);}
}while(T--){solve();}return 0;
}