2026.01.01 C. Yum Yum Numbers

C. Yum Yum Numbers
将整数x拆解为质数相乘的结果，质数的幂次能被2整除几次，莲花率就是几，要获得最大莲花率，就要获得最大的n使得h*2的n次幂。
1.预处理 用线性筛获取合数乘的最大质数。

点击查看代码

vector<int>pri(M);
//pri[i] = i;
for(int i = 2;i <= M;++i){if(pri[i] == i)//i为质数for(int j = i + i;j <=M;j += i){//将i的倍数等于ipri[j] = i;}
}

接下来将x分解为质数相乘，因为我们关心的是最后的数能开几次根号（幂次能除几次二分之一）所以这里我们只保存质数的幂次。

点击查看代码

vector<long long>cmp;
while(x > 1)
{int cnt = 0;int p = pri[x];while(x % p == 0){x /= p;cnt++;}cmp.empace_back(cnt);
}

接下来就是对cmp操作，每次操作向能开ans + 1次根号靠近,，当操作次数大于k时，break

点击查看代码

int ans = 0,cnt = 2;
while(true){long long tmp = 0;for(auto &x:cnt){long long val = (x + cnt - 1) / cnt;//在第ans + 1次操作中，使幂次能整除cnt（2的ans+1次幂）tmp = val * cnt - x;//需要的操作次数x = val * cnt;}if(tmp > k)break;k -=tmp;ans++;cnt *= 2;
}