题面如下：

思路 or 题解

$x^k=a_i$
我们可以去想办法去找到 最小的$x$
为什么去寻找$x_{min}$
看样例：
$521=8^3$
$521=2^9$
一个数如果满足式子 $x^k=a_i$ 至少我们可以找到一个$x$
如果有多个$x$我们其实只需要记录最小的那个就行

思路一： 二分

通过二分来找到$x_{min}$

AC代码如下：

const int N = 100009;
int n;
set<int> s;
bool check(int mid, int x, int k)
{int res = 1;for (int i = 1; i <= k; i++){res *= mid;if (res >= x){return true;}}return false;
}
bool work(int x, int k)
{int l = 1, r = 5e4;while (l < r){int mid = l + r >> 1;if (check(mid, x, k))r = mid;elsel = mid + 1;}int res = 1;for (int i = 1; i <= k; i++){res *= r;if (res > x)return false;}if (res == x)return true;return false;
}
bool check2(int mid, int k, int x)
{int res = 1;for (int i = 1; i <= k; i++){res *= mid;if (res >= x){return true;}}return false;
}
int cal(int k, int x)
{int l = 2, r = 5e5;int mid = l + r >> 1;while (l < r){int mid = l + r >> 1;if (check2(mid, k, x))r = mid;elsel = mid + 1;}return r;
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++){int tt;cin >> tt;if (tt == 1){s.insert(1);continue;}for (int j = 29;; j--){if (work(tt, j)){s.insert(cal(j, tt));break;}}}cout << s.size() << '\n';
}
signed main()
{buff;solve();
}

思路二：预处理

$x^k\le 1e9$** $x^k$ 数量其实不大
我们可以通过预处理来得到 $a_i的x_{min}$

AC代码如下：

typedef long long ll;
int main()
{ll n;cin >> n;map<ll, ll> mp;// 预处理出来所有的情况mp[1] = 1;for (ll i = 2; i <= 100000; i++){if (mp[i] == 0){for (ll j = 2; pow(i, j) < 1e9 + 7; j++){mp[pow(i, j)] = i;}}}set<ll> st;for (ll i = 0; i < n; i++){ll x;cin >> x;st.insert(mp[x]);}cout << st.size();
}