题意:1997/1998欧洲西南部地区比赛(乌尔姆举行的)后发生一个大的竞赛党。组织团队发明了一种特殊的模式,选择那些洗的脏盘子,以协助参与者。参赛者将在队列中排队,一前一后。每位选手得到了一个数字,从2开始第一个,第二个,第三,等等,连续
在队列中的第一个选手问他的电话号码(2)。他被释放从洗涤和派对,但他身后的每一个第二的选手不得不去厨房(4,6,8,等)。然后剩余的队列中的下一个选手必须要告诉他的电话号码。他回答3和协助被释放,但他后面的选手每三是帮助(这些数字9,15,21等)。剩下的队列中的下一个有5号,是免费的,但他身后的每一个第五选手被选中(那些用数字19,35,49等)。接下来的7号是免费的,但每一个在他身后的第七协助,等等。我们拨打该号码的选手,谁不需要协助洗了一个幸运数字。继续选择方案,幸运数字是顺序2,3,5,7,11,13,17,等要准备接下来的比赛方的幸运数字。
原题http://acm.hdu.edu.cn/showproblem.php?pid=1216
题解:先用筛选法模拟求出这样的幸运数;
错误分析:数组要开的大一些;但也不能太大;
#include<cstdio> #include<cstring> using namespace std; #define MAX 35000 typedef long long ll; int prime[MAX]; ll lucky[MAX]; void init() { memset(prime,0,sizeof(prime)); int i,j,k=0; for(i=2;i<MAX;i++ ) { if(!prime[i]) { lucky[++k]=i; prime[i]=1; int count=0; for(j=i+1;j<MAX;j++) { if(!prime[j]) { count++; if(count==i)//标记,每i个从中清除 { prime[j]=1; count=0; } } } } } } int main() { init(); int n; while(scanf("%d",&n),n) printf("%lld\n",lucky[n]); return 0; }