P9836 种树题解

huangqixuan / 2024-02-29 / 原文

题目传送门

前置知识

质因数分解。
贪心。

题解

思路

先来解决一个问题，统计一个数 $x$ 的正因数个数。可以将 $x$ 质因数分解，得到每个数在 $x$ 的质因数分解中出现了多少次。都知道质因数分解是每个数的唯一分解，那么统计个数的时候就只需要枚举每个质因数的出现个数。所以 $x$ 的正因数个数就是每个数在 $x$ 的质因数分解中出现次数 $+1$ 后的乘积。代码如下：

long long ans = 1;
for(int x = 1; x <= n; x++){
  for(Pair y : sum[x]){
    ans *= y.second + 1, ans %= mod;
  }
}
cout << ans;

那么贪心就慢慢显露出来了。

题目中给的 $w$ 我们可以对其进行质因数分解（因为给一个数乘以 $w$ 的某个正因数，就是从 $w$ 的质因数分解中取出一下数相乘）。由于质因数分解后的个数最多是 $\log w$ 个，所以可以暴力枚举每个质因数，对其贪心地选择乘到某棵树的高度上。

贪心就需要考虑一个质数乘到某棵树的高度上对答案的影响。这个质数 $k$ 如果乘到第 $i$ 棵树的高度上，就会给 $p_i$ 的质因数分解中 $k$ 的出现次数 $+1$。

设出现次数在 $+1$ 之前是 $s$，则 $+1$ 后答案 $ans$ 会变为 $ans + \frac{ans}{s+1}$，所以要尽量使 $s$ 更小，这就是贪心了。

在贪心的时候需要注意如果 $k$ 在 $p_i$ 的质因数分解中没有出现，那么 $s = 0$，记得判断一下。

最后时间复杂度为：$O(n \times \log w \times \log p_i)$

Code

#include <bits/stdc++.h>

using namespace std;
using LL = long long;
using Pair = pair<int, int>;

const int MAXN = 1e4 + 3;
const LL mod = 998244353;

int n, w;
vector<Pair> sum[MAXN]; // 每个 p_i 的质因数（first:质因数值  second:个数)

void Change(int i){ // 贪心
  Pair Mid;
  int Mw = 1e9 + 7;
  for(int x = 1; x <= n; x++){
    bool ooo = 0;
    for(int y = 0; y < sum[x].size(); y++){ // 直接暴力枚举
      if(sum[x][y].first == i && Mw > sum[x][y].second){
        Mid = {x, y}, Mw = sum[x][y].second;
      }
      if(sum[x][y].first == i) ooo = 1; // 判断 i 是否没有出现
    }
    if(ooo == 0){
      Mw = 0, Mid = {x, -1};
      break;
    }
  }
  if(Mw < 1e9){
    if(Mid.second == -1){
      sum[Mid.first].push_back({i, 1}); // 新建
    }else sum[Mid.first][Mid.second].second++;
  }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
  //freopen("plant3.in", "r", stdin);
  cin >> n >> w;
  for(int i = 1, P; i <= n; i++){
    cin >> P;
    for(int j = 2, cnt; j * j <= P; j++){ // 质因数分解 P
      if(P % j == 0){
        cnt = 0;
        while(P % j == 0) P /= j, cnt++;
        sum[i].push_back({j, cnt});
      }
    }
    if(P > 1) sum[i].push_back({P, 1}); // 质因数分解的最后要记得加上哦
  }
  for(int i = 2; i * i <= w; i++){ // 质因数分解 w
    if(w % i == 0){
      while(w % i == 0) w /= i, Change(i);
    }
  }
  if(w > 1) Change(w); // 质因数分解的最后要记得加上哦
  LL ans = 1;
  for(int x = 1; x <= n; x++){ // 统计答案
    for(Pair y : sum[x]){
      ans *= y.second + 1, ans %= mod;
    }
  }
  cout << ans;
  return 0;
}