超指数|试填法

lc

lc3020

也可以开平方写，但是效率不如乘法(

统计数组元素频次，先处理数字1得到最长奇数长度，再对其余数不断取平方并统计可连续平方的次数

计算最长奇数长度的平方链，最终返回最大长度

int ans = cnt[1] - 1 | 1; // 奇数

将数字1的频次处理为不大于该频次的最大奇数，用位运算-1 | 1 快速实现奇数化

class Solution {

public:

int maximumLength(vector<int> &nums)

{

unordered_map<long long, int> cnt;

for (int x : nums)

cnt[x]++;

int ans = cnt[1] - 1 | 1; // 奇数

cnt.erase(1);

for (auto &[num, _] : cnt) {

int res = 0;

long long x = num;

for (; cnt.contains(x) &&cnt[x] > 1; x *= x) res += 2;

ans = max(ans,res + (cnt.contains(x) ? 1 : -1)); // 保证 res 是奇数

}

return ans;

}

};