【解题报告】2021牛客寒假算法基础集训营4

前面的话

比赛连接：2021牛客寒假算法基础集训营4
有些题目是自己思考做出来的，有些是看他人的思路自己做的，也有的是参考别人的代码然后写的。
我决定这里以及以后都会写出来，标记在思路右边。
不同解法的时间复杂度也不同，会标记在代码内。
如果是简单题或者复杂度(做出来的或者没做出来的)，我可能都会带一些补充，放在每题的后面。

A ：九峰与签到题 | 模拟 (签到题)

【题意】
求出任何时刻，通过率都 $\ge 50\%$ 的题目。
【细节】
判断通过率 $\ge 50\%$ 不建议这么写： $ac/all\ge0.5$
而是建议这么写： $2\times ac\ge all$

B：武辰延的字符串 | exKMP

【题意】
给你两个字符串 $s、t$
设 $s_i$ 表示字符串 $s$ 的长度为 $i$ 的前缀。
设 $s_i+s_j$ 表示 $s_i$ 和 $s_j$ 的直接拼接。
问你有多少对不同的 $i、j$ ，满足 $s_i+s_j=t_{i+j}$
【范围】 $1\le |s|,|t|\le 10^5$
【思路】赛内
首先如果能满足要求，一定要 $s_i=t_i$
接下来就是对于每一个位置 $i$ ， $s[1,2,...]$ 与 $t[i+1,i+2,...]$ 的最长公共前缀是多少。
暴力计算肯定会超时的，不过我们有 $exKMP$ ，可以快速计算。

【代码】
时间复杂度： $O(|s|+|t|)$
$12/1000Ms$

/* 求解 T 中 next[]，注释参考 GetExtend() */
void GetNext(string & T, int & m, int next[])
{
  int a = 0, p = 0;
  next[0] = m;

  for (int i = 1; i < m; i++){
      if (i >= p || i + next[i - a] >= p){
          if (i >= p)
              p = i;
          while (p < m && T[p] == T[p - i])
              p++;
          next[i] = p - i;
          a = i;
      }
      else
          next[i] = next[i - a];
  }
}
/* 求解 extend[] */
void GetExtend(string & S, int & n, string & T, int & m, int extend[], int next[])
{
  int a = 0, p = 0;
  GetNext(T, m, next);

  for (int i = 0; i < n; i++){
      if (i >= p || i + next[i - a] >= p){
          if (i >= p)
              p = i;
          while (p < n && p - i < m && S[p] == T[p - i])
              p++;
          extend[i] = p - i;
          a = i;
      }
      else
          extend[i] = next[i - a];
  }
}
int nxt[100050];
int extend[100050];
int main()
{
  string S, T;
  int n, m;

  cin >> T >> S;
  n = S.size();
  m = T.size();
  GetExtend(S, n, T, m, extend, nxt);

  long long res = 0;
  for (int i = 0; i < n; i++){
      if(S[i] == T[i])res += (long long)extend[i+1];
      else break;
  }
  cout << res;
  return 0;
}

【补充】
其实这题推荐解应该是二分查找+字符串哈希，不过 $exKMP$ 应该是时间最优解了。
不过后面有字符串哈希的题...

D ：温澈滢的狗狗 | 二分

【题意】
从左到右有 $n$ 个点，每个点有颜色 $c_i$
如果 $c_i\ne c_j$ ，那么点对 $(i,j)$ 之间有亲密度 $|i-j|$
我们把所有有亲密度的点对取出来，优先级按照 **亲密度从高到低， $i$ 从高到低， $j$ 从高到低** 排序。
问你亲密度排序后第 $k$ 对点对是哪两个点，或者告诉她不存在亲密度第 $k$ 的点对。
【范围】 $1\le n\le 10^5$
$1\le k\le \frac{n(n-1)}{2}$
$1\le c_i\le n$
【思路：第一步】参考题解
因为亲密度排序的最高优先级是亲密度大小，容易想到我们可能可以二分找出亲密度 $\le d$ 的异色点对个数，然后确定最终第 $k$ 对点对的亲密度的值是多少。
假设我们知道了最终亲密度为 $d$ ，且亲密度 $\le d-1$ 的点对数量 $m$ ，我们只要 $O(n)$ ，从左到右扫一遍距离为 $d$ 的点对，如果颜色不同那么 $m$ 自增 $1$ ，直到 $m=k$ 即可。
那么我们想知道怎么去**二分找亲密度 $\le d$ 的异色点对的个数**。
【思路：第二步】
首先，直接求很难求，我们根据容斥得到：**异色点对的个数 $=$ 所有点对个数 $-$ 同色点对个数**。
有 $n$ 个数，距离 $\le d$ 的所有点对个数是多少呢？假设距离为 $i$ ，我们得到这个式子： $all=\sum_{i=1}^d (n-i)=nd-\frac{(1+d)d}{2}$ 有 $n$ 个数，距离 $\le d$ 的同色个数是多少呢？
我们肯定枚举每一种颜色 $c$ ，然后用 滑动窗口 去计算距离 $\le d$ 的点对个数。
我们会事先把颜色为 $c$ 的点按照下标升序丢到 $Vector[c]$ 中预处理。
假设窗口左端、右端下标分别为 $st、ed-1$ ，我们新加进来下标为 $ed$ 的同色点。
如果新的窗口长度 $\le d$ ，那么新的点产生的点对个数为 $ed-st$ 。
如果新的窗口长度 $>d$ ，那么我们把窗口向右移动，直到距离合法，返回上一步。

【代码】
时间复杂度： $O(n\log n)$
$49/1000Ms$

const int MAX = 2e5+50;
int n;
ll k;
vector<int>V[MAX];
ll solve(int x,int d){
  int st = 0;
  ll res = 0;
  for(int ed = 1;ed < V[x].size();++st){
      while(ed < V[x].size() && V[x][ed] - V[x][st] <= d){
          res += ed - st;
          ed++;
      }
  }
  return res;
}
bool check(ll d){
  ll sum = (ll)n * d - (1+d)*d/2;
  for(int i = 1;i <= n;++i){
      if(V[i].size() >= 2)sum -= solve(i,d);
  }
  return sum >= k;
}
int aa[MAX];
int main()
{
  scanf("%d%lld",&n,&k);
  for(int i = 1;i <= n;++i){
      int t;scanf("%d",&t);
      aa[i] = t;
      V[t].push_back(i);
  }
  ll L = 1,R = n - 1;
  while(L < R){
      ll M = (L + R) >> 1;
      if(check(M))R = M;
      else L = M + 1;
  }
  ll tmp = (L-1) * n - (1+L-1)*(L-1)/2;
  for(int i = 1;i <= n;++i){
      if(V[i].size() >= 2)tmp -= solve(i,L-1);
  }
  for(int i = 1;i + L<= n;++i){
      if(aa[i] != aa[i+L])tmp++;
      if(tmp == k){
          printf("%d %d",i,i+L);
          return 0;
      }
  }
  printf("-1");
  return 0;
}

E：九峰与子序列 | $dp$ + 字符串哈希

【题意】
有一个目标字符串 $k$
有 $n$ 个字符串序列，分别为 $c_1\cdots c_n$
问你有多少种方案，选出一些子序列使其拼接起来形成 $k$ 串
【范围】 $|k|\le 5\times10^6$
$n\le 40$
$\sum|c_i|\le 5\times10^6$
【思路】赛内一些 + 参考题解
首先要读懂题意，是求子序列，即 $[a_1,a_2]$ 和 $[a_2,a_1]$ 是相同的一种。
把一些字符串拼成目标串？很有 $dp$ 的感觉了。
我们设 $dp[i][j]$ 表示**前 $i$ 个字符串序列拼成目标串到第 $j$ 位的方案数**
容易得到状态转移方程：
$dp[i][j]=dp[i-1][j]+dp[i-1][j-len(a_i)]\times Compare\Big( a_i[1,len(a_i)],k[j-len(a_i)+1,j] \Big)$
但是关键是这个比较特别花时间。那就用字符串哈希 ，然后比较哈希值吧。
然后注意到，空间复杂度 $O(n|k|)$ 是不大允许的，像背包算法一样，我们可以逆序滚动，把第一个维度给省略掉。

【代码】
时间复杂度： $O(n|k|+\sum|c_i|)$
空间复杂度： $O(|k|+\max|c_i|)$
$390/1000Ms$

const int MAX = 5e6+50;
const ll pri = 233;
char aim[MAX];
char aa[MAX];
unsigned long long hsh[MAX];
unsigned long long shs[MAX];
unsigned long long base[MAX];
ll dp[MAX];
int main()
{
  int n,k;scanf("%d%s",&n,aim+1);
  k = strlen(aim+1);
  base[0] = 1;
  for(int i = 1;i <= k;++i){
      hsh[i] = hsh[i-1] * pri + aim[i];
      base[i] = base[i-1] * pri;
  }
  dp[0] = 1;
  for(int i = 1;i <= n;++i){
      scanf("%s",aa+1);
      int ed = strlen(aa+1);
      shs[0] = 0;
      for(int j = 1;j <= ed;++j){
          shs[j] = shs[j-1] * pri + aa[j];
      }

      for(int j = k - ed + 1;j >= 1;--j){
          ll hash1 = hsh[j+ed-1] - hsh[j-1] * base[ed];
          if(hash1 == shs[ed]){
              dp[j+ed-1] += dp[j-1];
          }
      }
  }
  printf("%lld",dp[k]);
  return 0;
}

【补充】
特地去复习(预习)了一下字符串哈希，用双哈希直接 $TLE+MLE$ ，用单哈希还是 $TLE$
结果只能用 $ull$ 自然溢出了...
本题也可以用折半搜索去做，不过会比较麻烦。

F：魏迟燕的自走棋 | 并查集

【题意】
有 $n$ 个人， $m$ 个装备。每个人只能有一个装备，一个装备只能分配给一个人。
其中第 $i$ 件装备可以给 $k_i$ 个人，分别为 $p_1,\cdots,p_{k_i}$ ，装备了能总体增加 $w_i$ 战斗力。
问你总体战斗力最大值能为多少？
【范围】 $1\le n,m\le 10^5$
$1\le k_i\le 2$
$1\le w_i\le 10^9$
【思路】参考题解
我们把人当做点，装备当做边，就有了一个图。
我们如果不要某个装备，相当于把这条边给删掉。
我们最后的合法情况是什么情况？就是对于每一个连通图来说，要么： $n$ 个点连接 $n-1$ 条边，为一棵树(或者一个有自环的点) $n$ 个点连接 $n$ 条边，为一个基环树
~~按照出题人的结论~~ 按照贪心的思路，每次拿权值最大的边。如果是一个点，那么相当于删掉这个点。如果是两个不同的点，那么相当于把这两个点缩为一个点，可以通过并查集来实现。
为什么贪心可以呢？考虑一个合法方案，假设是一个基环树。
我们在树的任意地方添上一条权值大于树的所有边的新边。容易得到，我们都可以通过断掉一条小边，加上这条大边，使得最后得到的解合法且更大。

【代码】
时间复杂度： $O(m\log m)$
$49/1000Ms$

const int MAX = 2e5+50;
int fa[MAX];
bool used[MAX];
int find_fa(int x){
  if(x == fa[x])return x;
  return fa[x] = find_fa(fa[x]);
}
void add(int x,int y){
  int fx = find_fa(x);
  int fy = find_fa(y);
  if(fx != fy){
      fa[fx] = fy;
  }
}
bool sam(int x,int y){
  int fx = find_fa(x);
  int fy = find_fa(y);
  return fx == fy;
}
struct node{
  int ta,tb;
  ll w;
  bool operator <(const node &ND)const{
      return w > ND.w;
  }
}aa[MAX];
int main()
{
  int n,m;scanf("%d%d",&n,&m);
  for(int i = 1;i <= n;++i)fa[i] = i;

  for(int i = 1;i <= m;++i){
      int shu;scanf("%d",&shu);
      if(shu == 1){
          scanf("%d%lld",&aa[i].ta,&aa[i].w);
          aa[i].tb = aa[i].ta;
      }else{
          scanf("%d%d%lld",&aa[i].ta,&aa[i].tb,&aa[i].w);
      }
  }
  sort(aa+1,aa+1+m);
  ll res = 0;
  for(int i = 1;i <= m;++i){
      int x = find_fa(aa[i].ta);
      int y = find_fa(aa[i].tb);
      if(x != y){
          if(!used[x]){
              res += aa[i].w;
              used[x] = 1;
          }else if(!used[y]){
              res += aa[i].w;
              used[y] = 1;
          }
          fa[x] = y;
      }else{
          if(!used[x])
              res += aa[i].w;
          used[x] = 1;
      }
  }
  printf("%lld",res);
  return 0;
}

G：九峰与蛇形填数 | 差分 + 优先队列

【题意】
给定一个 $n\times n$ 的初始全 $0$ 的矩阵。
进行填数 $m$ 次。每次选择左上角为 $x_i,y_i$ ，填边长为 $k$ 的蛇形矩阵。
蛇形矩阵类似下图：
$\begin{bmatrix} 1&2&3\\ 6&5&4\\ 7&8&9 \end{bmatrix}$
最后输出最终的矩阵。
【范围】 $n<2000$
$m<3000$
$1\le x_i,y_i\le n$
$\max(x_i+k-1,y_i+k-1)\le n$
【思路】赛内想 + 来不及写了吃了个饭的时候想出来了
我们希望快速算出每一个位置 $(i,j)$ 最终是被哪一个矩形所覆盖的。
找了很久的二维线段树的区间置数+单点查询的板子，但是找不到...
我们二维区间差分可以做到给某一个矩形增加 $c$ ，但是也很难做到区间数字置为 $c$ 呀。
但是如果是一维的话，就好办了：
假设有多次操作，第 $i$ 次让编号为 $i$ 的矩形覆盖位置 $[x_i,y_i]$ 如果是这样的话我们怎么做呢？
因为编号依次增大，我们可以搞一个优先队列，每次最优先考虑编号最大的矩形。然后我们要获得每个位置分别是哪些矩形的开始位置 记录在 $vector[i]$ 中，以及每个矩形的最右范围 $MP[i]$ 。
这样，我们每次遇到 $vector[pos]$ 非空，就把矩形编号放进优先队列中去，还要判断队列中最大编号是否超过 $MP[i]$ 了，是的话直接把该矩形编号 $pop$ 掉。
二维怎么做呢？其实一样的！二维就是多个一维相加即可做，不要想复杂了。
然后得到每个位置的最终矩形编号，我们容易直接计算出该位置的数字。

【代码】
时间复杂度： $O(n^2\log m)$
$1107/2000Ms$

_            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
      __/ |
     |___/
const int MAX = 3e3+50;
struct node{
  int z,y;
  int bh;
};
struct node2{
  int a,b,k;
}bb[MAX];
vector<node>V[MAX];
vector<int> de[MAX];
int aa[MAX][MAX];
unordered_map<int,int>MP;
priority_queue<int>Q;
int main()
{
  int n,m;scanf("%d%d",&n,&m);
  for(int i = 1;i <= m;++i){
      int x,y,k;scanf("%d%d%d",&x,&y,&k);
      bb[i].a = x;
      bb[i].b = y;
      bb[i].k = k;

      for(int j = x;j <= x + k - 1;++j)
          V[j].push_back({y,y+k-1,i});
  }
  for(int i = 1;i <= n;++i){
      for(int j = 1;j <= n;++j)de[j].clear();
      MP.clear();
      while(!Q.empty())Q.pop();
      MP[0] = INF;
      for(int j = 0;j < V[i].size();++j){
          de[V[i][j].z].push_back(V[i][j].bh);
          MP[V[i][j].bh] = V[i][j].y;
      }

      Q.push(0);
      for(int j = 1;j <= n;++j){
          for(int k = 0;k < de[j].size();++k)
              Q.push(de[j][k]);
          while(MP[Q.top()] < j)Q.pop();

          aa[i][j] = Q.top();
      }
  }

  for(int i = 1;i <= n;++i){
      for(int j = 1;j <= n;++j){
          int shu = aa[i][j];
          if(shu == 0)printf("0 ");
          else{
              int hang = i - bb[shu].a + 1;
              int lie  = j - bb[shu].b + 1;
              int res = (hang-1)*(bb[shu].k);
              if(hang&1){
                  res+=lie;
              }else{
                  res+=bb[shu].k-lie + 1;
              }
              printf("%d ",res);
          }
      }
      puts("");
  }
  return 0;
}

H：吴楚月的表达式 | 树形 $dp$

【题意】
给定一颗有根树，根编号为 $1$
有 $n$ 个节点，每个节点有权值 $v_i$ ，每条边有一个操作符 $\{+-*/\}$ 中的一种。
问你从根出发到各个节点，表达式按照正常的优先级去计算，到各个节点的权值分别为多少。
对答案取模 $1e9+7$
【范围】 $1\le n\le 10^5$
$1\le v_i\le 10^9$
【思路】赛内
考虑到没有 $($ 和 $)$ 的括号的优先级干扰，我们把每个点的权值记录成 $a+b$ 的形式。
如果是乘法与除法，根据优先级，我们只对 $b$ 进行计算。
如果是加法与减法，根据优先级，我们把 $a$ 替换成 $a+b$ ，然后把 $b$ 替换该节点的权值，正负号表示加或者减。

【代码】
时间复杂度： $O(n)$
$55/1000Ms$

_            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
      __/ |
     |___/
const int MAX = 1e5+50;
ll q1[MAX],q2[MAX];
vector<int>V[MAX];
char op[MAX];
ll aa[MAX];
void dfs(int x){
  for(auto it : V[x]){
      if(op[it] == '+'){
          q1[it] = (q1[x] + q2[x]) % MOD;
          q2[it] = aa[it];
      }else if(op[it] == '-'){
          q1[it] = (q1[x] + q2[x]) % MOD;
          q2[it] = -aa[it] + MOD;
      }else if(op[it] == '*'){
          q1[it] = q1[x];
          q2[it] = q2[x] * aa[it] % MOD;
      }else if(op[it] == '/'){
          q1[it] = q1[x];
          q2[it] = q2[x] * inv(aa[it]) % MOD;
      }

      dfs(it);
  }
}
int main()
{
  int n;scanf("%d",&n);
  for(int i = 1;i <= n;++i)scanf("%lld",&aa[i]);
  for(int i = 2;i <= n;++i){
      int t;scanf("%d",&t);
      V[t].push_back(i);
  }
  scanf("%s",op+2);
  q1[1] = 0;q2[1] = aa[1];
  dfs(1);
  for(int i = 1;i <= n;++i){
      printf("%lld ",((q1[i] + q2[i]) % MOD + MOD) % MOD);
  }
  return 0;
}

I：九峰与分割序列 | $dp$ + 单调队列优化

【题意】嗯嗯题目挺言简意赅的就誊过来了
给定一个长度为 $n$ 的序列，将其分割成若干个子区间.
子区间的贡献为：若前一个子区间的长度 $>k$ 且该区间长度 $\le k$ ，则贡献为区间和的两倍，否则贡献为区间和。
第一个子区间的的前一个子区间长度视为 $0$ 。
求一种分割方法，使得所有子区间贡献之和最大，输出最大贡献。
【范围】 $k\le n\le 10^5$
$a_i\le 10^9$
【思路】题解 + 代码
这题貌似是除了魔方模拟外最难的题目了...我也理解了很久。
容易想到，我们设一个 $dp[i][j]$ ，表示： $dp[i][0]$ 表示到 $i$ 位置为止，且最后一个区间长 $\le k$ 的最大贡献 $dp[i][1]$ 表示到 $i$ 位置为止，且最后一个区间长 $> k$ 的最大贡献
更新也很好想到： $\begin{aligned} dp[i][0]&=\max \begin{cases} sum[j\sim i] + dp[j-1][0]\\ 2*sum[j\sim i]+dp[j-1][1] \end{cases}&i-j+1\le k\\ dp[i][1]&=\max \begin{cases} sum[j\sim i] + dp[j-1][0]\\ sum[j\sim i]+dp[j-1][1] \end{cases}&i-j+1> k\\ \end{aligned}$ 最终答案为 $\max(dp[n][0],dp[n][1])$
这样子貌似要用好多个线段树去维护，挺麻烦的。我们换一种设法：
设 $ans[i]=\max(dp[i][0],dp[i][1])$ ，设 $f[i]=dp[i][1]$
这样转移就变成了： $\begin{aligned} ans[i]&=\max \begin{cases} ans[i-1]+num[i]\\ 2*sum[j\sim i]+f[j-1]&i-j+1\le k \end{cases}\\ f[i]&=ans[i-k-1]+sum[i-k\sim i] \end{aligned}$ 唔呼，每行都巧妙地别有深意 ~~???~~
这个时候，我们发现唯一的麻烦就是去转移那个 $ans[i]$ 的第二行了。
我们直接用单调队列 去维护那个最大的 $2*sum[j\sim i]+f[j-1]$ 就可以了。
为什么是单调队列呢？因为我们有 $i-j+1\le k$ 且需要求那个表达式的最大值。

【代码】
时间复杂度： $O(n)$
$21/1000Ms$

const int MAX = 5e6+50;
int num[MAX];
ll pre[MAX];
int L,R;
int deq[MAX];
ll ans[MAX],f[MAX];
int main()
{
  int n,k;scanf("%d%d",&n,&k);
  for(int i = 1;i <= n;++i){
      scanf("%d",&num[i]);
      ans[i] = f[i] = pre[i] = pre[i-1] + num[i];
  }
  L = 0;R = 0;
  deq[R++] = k + 1;
  for(int i = k + 2;i <= n;++i){
      while(L < R && i - deq[L] > k)L++;
      ans[i] = max(f[deq[L]] + 2 * (pre[i] - pre[deq[L]]),ans[i-1] + num[i]);
      f[i] = ans[i - k - 1] + pre[i] - pre[i - k - 1];
      while(L < R && f[deq[R-1]] + 2 * (pre[i] - pre[deq[R-1]]) < f[i])R--;
      deq[R++] = i;
  }
  printf("%lld",ans[n]);
  return 0;
}

J：邬澄瑶的公约数 | 数论

【题意】
求
$\gcd(x_1^{a_1},x_2^{a_2},\cdots,x_n^{a_n})$
答案取模 $1e9+7$
【范围】 $1\le n,x_i,a_i\le 10^4$
【思路】赛内
考虑到 $gcd$ 的本质就是求出 $\prod\{p_1^{\min s_1},p_2^{\min s_2},\cdots,p_t^{\min s_t}\}$ ，求出每个质数的最小幂次。
我们算出每个质数的最小幂次，乘起来即可。
其实细想只要 $O(n\sqrt n)$ 的暴力判断代码即可，我这个由于是第二题，直接瞎敲敲就随意了ww

【代码】
时间复杂度： $O(\frac{n^2}{\log n})$ 带优化，卡不卡估计都能过 $7/1000Ms$ 虽然过的飞快

_            __   __          _          _
| |           \ \ / /         | |        (_)
| |__  _   _   \ V /__ _ _ __ | |     ___ _
| '_ \| | | |   \ // _` | '_ \| |    / _ \ |
| |_) | |_| |   | | (_| | | | | |___|  __/ |
|_.__/ \__, |   \_/\__,_|_| |_\_____/\___|_|
      __/ |
     |___/
const int MAX = 2e4+50;
int cnt;
bool vis[MAX];
int prime[MAX];
int shu[MAX];
int xx[MAX],pp[MAX];
void shai(int n){
  for(int i = 2;i <= n;++i){
      if(!vis[i]){
          prime[++cnt] = i;
      }
      for(int j = 1;j <= cnt && i * prime[j] <= n;++j){
          vis[i * prime[j]] = 1;
          if(i % prime[j] == 0)break;
      }
  }
}
int main()
{
  int n;scanf("%d",&n);
  shai(10000);
  for(int i = 1;i <= cnt;++i)shu[i] = INF;
  int mn = INF;
  for(int i = 1;i <= n;++i)scanf("%d",&xx[i]);
  for(int i = 1;i <= n;++i)scanf("%d",&pp[i]);

  for(int i = 1;i <= n;++i){
      int t = xx[i];
      int p = pp[i];
      for(int j = 1;j <= cnt;++j){
          if(prime[j] > t){
              mn = min(mn,j-1);
              break;
          }
          int ci = 0;
          while(t % prime[j] == 0){
              ci++;
              t /= prime[j];
          }
          ci *= p;
          shu[j] = min(shu[j],ci);
      }
  }
  ll res = 1;
  for(int i = 1;i <= mn;++i){
      res = res * qpow(prime[i],shu[i]) % MOD;
  }
  printf("%lld",res);
  return 0;
}

参考

【题解】2021年牛客寒假集训营第四场题解

【解题报告】2021牛客寒假算法基础集训营4

【解题报告】2021牛客寒假算法基础集训营4

前面的话

A ：九峰与签到题 | 模拟 (签到题)

B： 武辰延的字符串 | exKMP

D ：温澈滢的狗狗 | 二分

E： 九峰与子序列 | + 字符串哈希

F： 魏迟燕的自走棋 | 并查集

G：九峰与蛇形填数 | 差分 + 优先队列

H：吴楚月的表达式 | 树形

I：九峰与分割序列 | + 单调队列优化

J：邬澄瑶的公约数 | 数论

参考

B：武辰延的字符串 | exKMP

E：九峰与子序列 | $dp$ + 字符串哈希

F：魏迟燕的自走棋 | 并查集

H：吴楚月的表达式 | 树形 $dp$

I：九峰与分割序列 | $dp$ + 单调队列优化