本文共 2597 字，大约阅读时间需要 8 分钟。
这道题题意对于一般的ACMER应该不是什么问题吧！
首先是个约瑟夫问题的升级版
1）.告诉你第一次是顺时针第k个人出队
2）.某个人（编号为 i） 出队后，下个出队的是从这个开始查第num[i]个人，若num[i]<0,为逆时针数，否则顺时针数。
3）.重复步骤2）.，直到全部出队。
4）.输出出队序号中，那个序号的约数最多的那个人名及约数个数。
这里需要知道一个知识：反素数。
详见
有了反素数，我们就知道那个序号为最终答案了。
怎么求出那个序号是谁呢？对于这个，目前我只知道用模拟来找出。
思路:每次找出第几个需要要出队的人得位置，然后根据位置，找到下个需要出队的位置。
详见代码：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 using namespace std; 9 const int maxn = 500555; 10 char name[maxn][12]; 11 int num[maxn]; 12 int rprim[35][2] = { 13 498960,200,332640,192,277200,180,221760,168,166320,160, 14 110880,144,83160,128,55440,120,50400,108,45360,100, 15 27720,96,25200,90,20160,84,15120,80,10080,72, 16 7560,64,5040,60,2520,48,1680,40,1260,36, 17 840,32,720,30,360,24,240,20,180,18, 18 120,16,60,12,48,10,36,9,24,8, 19 12,6,6,4,4,3,2,2,1,1}; 20 21 //1.bulid(); 22 //2.query(a,b) 23 //3.update(a,b) 24 #define lson l , m , rt << 1 25 #define rson m + 1 , r , rt << 1 | 1 26 27 int sum[maxn<<2]; 28 int n,k; 29 //根据题意做相关修改，询问时的操作 30 int operate(int a,int b){ 31 return a+b; 32 } 33 void PushUp(int rt){ 34 sum[rt]=operate(sum[rt<<1],sum[rt<<1|1]); 35 } 36 void bulid(int l=1,int r=n,int rt=1){ 37 if(l==r){ // 据题意做相关修改 38 sum[rt]=1;return ; 39 } 40 int m=(l+r)>>1; 41 bulid(lson); 42 bulid(rson); 43 PushUp(rt); 44 } 45 void update(int p,int add=0,int l=1,int r=n,int rt=1){ 46 if(l==r){ // 据题意做相关修改 47 sum[rt]=add;k=l; 48 //printf("k=%d\n",k); 49 return ; 50 } 51 int m=(l+r)>>1; 52 if(p<=sum[rt<<1])update(p,add,lson); 53 else update(p-sum[rt<<1],add,rson); 54 PushUp(rt); 55 } 56 57 int query(int L,int R,int l=1,int r=n,int rt=1){ 58 if(L<=l && r<=R){ 59 return sum[rt]; 60 } 61 int m=(l+r)>>1; 62 int ret=0; 63 if(L<=m)ret=operate(ret,query(L,R,lson)); 64 if(R> m)ret=operate(ret,query(L,R,rson)); 65 return ret; 66 } 67 68 int main(){ 69 int p,x,now,leftnum,rightnum,m; 70 while(~scanf("%d%d",&n,&k)){ 71 p=0; 72 while(n 0)num[k]=m; 89 else num[k]=1; 90 }else{ 91 num[k]%=m; 92 if(num[k]<0)num[k]+=m+1; 93 } 94 leftnum=query(1,k);//找出now左边有多少个人 95 rightnum=m-leftnum; 96 //printf("num[%d]=%d left=%d right=%d\n",k,num[k],leftnum,rightnum); 97 if(num[k]<=rightnum){ 98 now=leftnum+num[k]; 99 }else{100 now=num[k]-rightnum;101 }102 }103 update(now);104 printf("%s %d\n",name[k],rprim[p][1]);105 106 }107 108 return 0;109 }110 /*111 4 1112 Tom 2113 Jack 4114 Mary -1115 Sam 1116 */
转载于:https://www.cnblogs.com/tiankonguse/archive/2012/07/29/2613871.html
View Code