代码源 每日一题 div1 Rad

题目链接

Rad

思路

这题应该是构造+数论

先考虑$rad(n)$这个函数，什么情况下满足$rad(n)<n$，如果把n进行质因子分解的话，会变成这样的形式$p_1^{k_1}?p_2^{k_2}?...?p_n^{k_n}$。可以发现，但凡有一个$k_i>=2$，那么就会有$rad(n)<n$。

有了这个观察，对于n，我们只需要找一个二次项的质因子即可。即找到$n=p^2?q$，那么怎么利用这个东西构造呢？

由于题目中询问的是$rad(a?b?n)<n(a+b=n)$，我们尽量把a,b凑成$p^2?q$的形式。

那么可以构造$a=p?(p?1)?q,b=p?q$, 这样满足了$a+b=n$

$rad(a?b?n)=rad(p?(p?1)?q?p?q?p^2?q)=rad(p^4?(p?1)?q^3)=rad(p?(p?1)?q)<p?(p?1)?q<n$

巧妙地构造出了一组解！

由于n的范围比较大，分解n的时候，直接分解$p^2(p<=1e9)$即可。可是这样还是比较大。不妨直接枚举$<=1e6$的所有因子，如果它是平方因子的话，就是一组合法解，如果不是的话。就把这个因子加入$q$，如果枚举完都找不到的话，看看n剩下的数能不能变成平方因子即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
typedef long long LL;
const LL INF = 1e18;
typedef pair<int,int> PII;
using tp = tuple<int,int,int>;
bool multi = true;LL n;
int pr[N], cnt;
bool st[N];
void get_primes(int n) {
    for(int i = 2; i <= n; i++) {
    if(!st[i]) pr[cnt++] = i;for(int j = 0; pr[j] * i <= n; j++) {
    st[pr[j] * i] = true;if(i % pr[j] == 0) break;}}
}void solve() {
    cin >> n;for(int i = 0; i < cnt && pr[i] <= n; i++) {
    LL pp = (LL)pr[i] * pr[i];if(n % pp == 0) {
    puts("YES");return;}if(n % pr[i] == 0) {
    n /= pr[i];}}LL v = sqrt(n);if(v > 1 && v * v == n) puts("YES");else puts("NO");}int main()
{
    
#ifdef ONLINE_JUDGE
#else freopen("F.txt", "r", stdin);
#endif
get_primes(N - 1);// ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);int T = 1;if(multi) cin >> T;while(T--) solve();return 0;
}