// 给我们一个正整数数组 数组长度>=2 数组元素>=1 <=1e9
// 问能组成x x^2 x^4 ... x^(k/2) x^k x^(k/2) ... x^4 x^2 x形式的合集
// 最多有几个元素
// 讲解一下这个合集的形式 以x为基数 除了x其他数的幂数都是2的幂
// 光看幂的话 他们的规律就是2^0 2^1 2^2 ...2^log(2,k).. 2^2 2^1 2^0
// 集合总数必然是奇数
// 如果理解成+2+2就不对了
// 该怎么做呢
// 从数据范围来看 数组元素最大不过1e9
// 也就是说能组成的集合 就算最大值是2^32 那么集合也不过63
// 实际上根本到不了 总数只能更小 那么暴力就行了
// 枚举2~...sqrt(max)作为基数的情况
// 再枚举幂数 看看数组中有无幂为x的数可以加入集合
// 每轮枚举完更新ans
// 再加一点点优化即可
// 提供一个输入数据
// [2,2,4,4,16,16,256,256,3,3,9,9,81,81,6561,6561,43046721,43046721]
// 答案应为9
class Solution {
public:
int mlog(int a,int b) {//return log_a(b) min(a,b)>1
double x1=log(a);
double x2=log(b);
if (x2<1e-4) return -1;
double t=x2/x1;
return (int)t;
}
int maximumLength(vector<int>& num) {
int ans,mxa;
unordered_map <int,int> mp;//统计各个值出现了多少次 数组长度1e5存的下
for (auto x:num) {
mp[x]++;
mxa=max(mxa,x);//找到最大值 命名为mxa是避免和max函数发生冲突
}
ans=mp[1];
if (ans%2==0) ans--;//特判一下1组成合集的情况 1的话无论几次幂都是1 所以是能找出的最大奇数个1就是答案 集合元素必然是奇数
ans=max(1,ans);
int len=sqrt(mxa);//len就是能组成集合的最大基数
for (int i=2;i<=len;i++) {//开始从底数枚举
int k=mlog(i,mxa);//以i为基数 理论上最大的幂
if (k%2) k--;
if (mlog(2,k)*2+1<ans) break;//如果理论上能组成的集合数都小于ans
//那么后面都不用推了 随着基数增大 能组成的合集大小只会越来越小
int cnt=0;
for (int j=1;j<=k;j*=2) {//枚举幂数 不断枚举 直到没有可以加入集合的数
int now=pow(i,j);
if (mp[now]>=2) {//说明now不论当不当最大值都可以加入集合
cnt+=2;
}
else {
if (mp[now]==1) cnt++;//now要当集合最大值
else cnt--;//没有now可以加入集合当最大值 回退一下
break;
}
}
if (cnt%2==0) cnt--;
ans=max(ans,cnt);
}
return ans;
}
};