1、划分循环数组

思路和********** 的子数组一样，只是目标和为循环数组和的一半。

2、n个学生围成一圈，编号从1到n。每个学生将从1开始报数，报到素数的人出列，剩下的人继续报数，试求最终留下来的人的编号是多少

这道题是一道典型的模拟题，难点在于判断素数，这里使用的是欧拉筛先打了一个素数表，时间复杂度为O(nlogn)。

#include <bits/stdc++.h>
using namesapce std;
const int N = 1e6 + 500;
int prime[N] = {0}; // prime[index] = 0,index为素数； prime[index] = 1，index为合数

void get_prime()
{
    for (int i = 2; i < N; ++i)
    {
        if (prime[i] == 0)
        {
            for (int j = i + i; j < N; j += i)
            {
                prime[j] = 1;
            }
        }
    }
}

int main() {
  get_prime();
  prime[1] = 1;
  int n;
  cin >> n;
  for (int i = 1; i <= n; i++) {
    que.push(i);
  }
  int count = 1; // 模拟报数
  while (que.size() > 1) {
    if (prime[cut] == 1) {
      que.push(que.front()); // 模拟合数不出列
    }
    que.pop();
    count++;
  }
  cout << que.front() << endl;
}

3、给定一个数组，你可以进行最多k次以下操作：“选择一个大于1的元素ai，使得ai除以它的一个素因子p”，试求操作结束后，数组的所有元素之和的最小值是多少？

这道题的解题思路是贪心，每次选择一个收益最大的数进行操作，确定了解题思路之后还需要考虑的点是获取数的最大素因子，这里也使用欧拉筛先打一个最大素因子的表。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 500;
int prime[N];
void Prime()
{
    for (int i = 2; i < N; ++i)
    {
        if (prime[i] == 0)
        {
            for (int j = i; j < N; j += i)
            {
                prime[j] = i;
            }
        }
    }
}
typedef struct Node
{
    int data;
    int prime;
    Node(){}
    Node(int _data, int _prime)
    {
        data = _data;
        prime = _prime;
    }
    friend bool operator<(const Node& a, const Node& b)
    {
        return (a.data - a.data/a.prime) < (b.data - b.data/b.prime);
    }
} node;
priority_queue<node> q;
int main()
{
    Prime();
    int n, k;
    cin >> n >> k;
    for (int i = 0; i < n; ++i)
    {
        int x;
        cin >> x;
        node a;
        a.data = x;
        a.prime = prime[x];
        q.push(a);
    }
    while (k)
    {
        int x = q.top().data;
        x = x / q.top().prime;
        q.pop();
        node y;
        y.data = x;
        y.prime = prime[x];
        q.push(y);
        k--;
    }
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        ans += q.top().data;
        q.pop();
    }
    cout << ans << endl;
}