\(\mathcal {P14214\ \ [COI 2010]\ \ 圆圈 \ \ /\ \ KOLO}\)
#include<bits/stdc++.h>
using namespace std;const int N=5e6+10;
int pre[N],nxt[N];
int n,k,a;
vector<int>p;
const int M=1e7;//5e5th prime
bool is_prime[M];void del(int x){pre[nxt[x]]=pre[x];nxt[pre[x]]=nxt[x];
}void add(int x,int a,int b){//a->b//a->x->bnxt[a]=x;nxt[x]=b;pre[x]=a;pre[b]=x;
}void seize(){int cnt=0,pos=2;while(cnt<=k){if(!is_prime[pos]){p.push_back(pos);cnt++;}for(auto j:p){if(pos*j<=M)is_prime[pos*j]=1;}pos++;}
}void init(){//1->2->3->4->5->1for(int i=1;i<=n;i++)nxt[i]=i+1;for(int i=1;i<=n;i++)pre[i]=i-1;pre[1]=n;nxt[n]=1;seize();
}main(void){ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cin>>n>>k>>a;init();int now=1,to;for(auto v:p){to=}
}/**
题目描述
年轻数学家聚会时常玩的一个游戏叫“素数圆圈”。游戏中有编号 1 到 N 的数学家站成一个大圆。开始游戏前，我们画有 N−1 个圆圈和 1 个正方形，正方形中站的是玩家 1，圆圈中站着从玩家 2 开始的其他人，他们逆时针排成大圆，面向中间。游戏进行 K 轮。在第 i 轮中，方格中的人跳起来说“到我了！”，然后连续 p_k
次与他右边的人交换位置，其中 p_k是第 k 个素数。例如 N=5,K=3 时： 第 1,2,3 轮按素数 2,3,5 次交换。
写一个程序，给定 N,K,A，输出最后编号为 A 的玩家左右两侧邻居的编号。输入格式
输入一行包含三个整数 N,K,A (1≤A≤N)，代表玩家的个数、轮数，以及指定查询的玩家。输出格式
输出一行两个整数，表示游戏结束后编号为 A 的玩家右侧和左侧相邻的玩家编号。输入输出样例
输入 #1
5 3 1
输出 #1
3 5
输入 #2
5 3 2
输出 #2
5 4
输入 #3
5 4 5
输出 #3
3 2
说明/提示
对于 25% 的数据，有 3≤N≤1 000,1≤K≤1 000。对于另外 25% 的数据，有 3≤N≤1 000,1≤K≤50 000。对于另外 25% 的数据，有 3≤N≤50 000,1≤K≤50 000。对于 100% 的数据，有 3≤N≤5 000 000,1≤K≤500 000。
*/