【链接】 我是链接,点我呀:)
【题意】
在这里输入题意
【题解】
让你在n的因子里面找一个最大的数字x
且x的因子全都不是完全平方数(y^2,y>1)
O(sqrt(n))找出n的所有因子。
然后O(sqrt(n))处理出1..N内的所有完全平方数。->用map存
对于x,看看它的因子里面有没有完全平方数
没有的话,ans = max(ans,x)
【代码】
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll ma = 1e12;
ll n;
vector <ll> v;
map<ll,int> is;
int main()
{
for (ll i = 2;i*i<=ma;i++) is[i*i]=1;
cin >> n;
ll t = sqrt(n);
for (int i = 1;i <= t;i++){
if (n%i==0){
v.push_back(i);
if (n/i!=i) v.push_back(n/i);
}
}
ll ma = 0;
for (ll x:v){
bool ok = true;
ll tt = sqrt(x);
for (int i = 1;i <= tt;i++)
if (x%i==0){
if (is[i]==1||is[x/i]==1){
ok = false;
break;
}
}
if (ok) ma = max(ma,x);
}
cout <<ma<<endl;
return 0;
}