2026.01.01 C. Yum Yum Numbers

C. Yum Yum Numbers
因为每k次操作能乘一个质数，所以将整数x拆解为质数相乘，\(m = b \times 2^{n}\)，质数的幂次能被2整除几次，莲花率就是几，要获得最大莲花率，就要获得最大的n使得h*2的n次幂。
1.预处理 用线性筛获取合数乘的最大质数。

点击查看代码

vector<int>pri(M);
iota(pri.begin(), pri.end(), 0);//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的倍数等于i
    pri[j] = i;
  }
}

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

点击查看代码

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

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

点击查看代码

int ans = 0;
long long 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;
}