[Croatian Olympiad in Informatics 【kolo】]【找规律】【正模拟】【逆模拟】

【题目链接】
http://www.hsin.hr/coci/
提交地址：http://evaluator.hsin.hr/
【题目大意】
1..n的n个数站成一个圈。
一共进行k轮
对于第i轮
选取位于最顶端的数。
他和自己逆时针方向相邻的那个数交换，一直交换pl[i]次。 其中pl[i]为第i个质数。
输入n,k,A。
A表示一开始的第A个数。
问进行了k轮以后，A的两个邻居是谁？
【算法分析】
假如n<=10^5，那么还可以用平衡树模拟搞一下。
但是n超大，所以不能如此。
质数自然是用筛法筛出来了。
然后我们可以先搞出A最后到了哪里。然后算出他的邻居，最后再逆回来，看一开始在哪里，就可以知道编号了。
然后具体的，容易发现，假如经过n*(n-1)次交换，那么相当于没动。
所以每次处理可以讲交换次数先%(n*(n-1))。  这里小心会爆int。
然后我们可以发现每转n次，那么将相当于忽略了顶端的那个数以后，都向顺时针转了一格。
于是首先是模拟转了p/n次以后的。
最后模拟剩下的转圈。这个不容易想。

然后逆回去将相当于反过来做了。。。
【其它】第一次交，95分。原因是我%(n*n)而不是%(n*(n-1))。。。居然这都有这么高分。。。泪流满面。
【Record】
est # Score Time Memory Result 1 5 0.52s 10392 kB Correct! 2 5 0.52s 10392 kB Correct! 3 5 0.52s 10392 kB Correct! 4 5 0.52s 10392 kB Correct! 5 5 0.52s 10392 kB Correct! 6 5 0.52s 10392 kB Correct! 7 5 0.53s 10392 kB Correct! 8 5 0.54s 10392 kB Correct! 9 5 0.54s 10392 kB Correct! 10 5 0.54s 10392 kB Correct! 11 5 0.53s 10392 kB Correct! 12 5 0.53s 10392 kB Correct! 13 5 0.54s 10392 kB Correct! 14 5 0.54s 10392 kB Correct! 15 5 0.54s 10392 kB Correct! 16 5 0.60s 10392 kB Correct! 17 5 0.66s 10392 kB Correct! 18 5 0.68s 10392 kB Correct! 19 5 0.67s 10392 kB Correct! 20 5 0.66s 10392 kB Correct! 【CODE】
#include #include #include #include using namespace std;
const int Size=7368789;
typedef long long lld;
int n,k,A,pt;
int pl[500005];
bool v[Size];

int Get(int x){return (x%n+n)%n;}

void Next(int &x,int p){
p=(int)(p%((lld)(n)*(n-1)));
if (x==0){
x=Get(p);
return;
}
x-=p/n;
if (x<=0) x--;
x=Get(x);
if (p%n>=x) x=Get(x-1);
}

void Pre(int &x,int p){
p=(int)(p%((lld)(n)*(n-1)));
if (p%n==x){
x=0;
return;
}
if (x x+=p/n;
if (x>=n) x=Get(x+1);
}

void Sai(){
memset(v,true,sizeof(v));
int i,j;
for (i=2;i for (j=i+i;j pt=0;
for (i=2;pt if (v[i]) pl[pt++]=i;
}

int main(){
int i,ans1,ans2;
// freopen("kolo.in.7","r",stdin);
// freopen("kolo.out","w",stdout);
cin >> n >> k >> A;
A–;
Sai();
for (i=0;i ans1=Get(A+1);
ans2=Get(A-1);
for (i=k-1;i>=0;i–){
Pre(ans1,pl[i]);
Pre(ans2,pl[i]);
}
cout << ans1+1 << " " << ans2+1 << endl;
}