• 1. 預(yù)處理每個(gè)數(shù)的最小質(zhì)因子，若沒(méi)有最小質(zhì)因子則為質(zhì)數(shù)輸出本身，否則輸出最小質(zhì)因子。

#include <iostream>
using namespace std;
const int N = 2e5 + 10;
int ans[N];
void solve()
{
  for (int i = 3; i <= 1e5; i++)
  {
    for (int j = 3; j * j <= i; j++)
    {
      if (i % j == 0)
      {
        ans[i] = j;
        break;
      }
    }
  }
}
int main()
{
  solve();
  int t;
  cin >> t;
  while (t--)
  {
    int x;
    cin >> x;
    if (x & 1)
    {
      cout << (ans[x] ? ans[x] : x) << endl;
    }
    else
    {
      cout << 2 << endl;
    }
  }
}
// 64 位輸出請(qǐng)用 printf("%lld")

• 2. 由于數(shù)組總和不變，要讓極差最小，最后極差必然是1，最后有sum%n個(gè)x+1和n-(sum%n)個(gè)x，按大小順序依次賦值即可。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 10;
#define int long long
int a[N];
signed main()
{
  int s = 0;
  int n;
  cin >> n;
  map<int, int> mp;
  for (int i = 1; i <= n; i++)
  {
    cin >> a[i];
    s += a[i];
    mp[a[i]]++;
  }
  int val = s / n;
  int y = s % n;
  int x = n - y;
  // cout<<x<<" "<<y<<endl;
  sort(a + 1, a + 1 + n);
  int m1 = 0, m2 = 0;
  for (int i = 1; i <= n; i++)
  {
    if (i <= x)
    {
      if (a[i] >= val)
        m1 += a[i] - val;
      else
        m2 += val - a[i];
    }
    else
    {
      if (a[i] >= val + 1)
        m1 += a[i] - val - 1;
      else
        m2 += val + 1 - a[i];
    }
  }
  cout << min(m1, m2);
}

• 重點(diǎn)是先手要怎么乘，使得后手不會(huì)占到便宜，后手肯定選子序列最小/最大的區(qū)間，這里太菜了沒(méi)想明白，感覺(jué)是dp，求大佬解答

upd：?jiǎn)柫舜罄兄更c(diǎn)會(huì)做了，實(shí)習(xí)兩個(gè)月整個(gè)人都變菜了

由于先手不會(huì)讓后手占便宜，選的區(qū)間肯定不會(huì)讓后手也能夠拿來(lái)用更優(yōu)，所以兩個(gè)人選的區(qū)間沒(méi)交集。先預(yù)處理pre_max[i]表示到i前綴的子序列最大值，pre_min[i]表示1-i前綴的子序列最小值，后綴同理，枚舉先手選的區(qū)間[i,j]，后手選的是[1,i-1]的最小/最大 和 [j+1,n]的最小/最大，兩者取min/max 取最小或最大由k的正負(fù)性決定

upd 經(jīng)過(guò)評(píng)論區(qū)大佬們指正 做法還是有問(wèn)題  等一個(gè)題解