题意：

　　一群小孩顺时针坐然后在玩约瑟夫环的游戏..

　　从第k个小孩开始..每个被选中的孩子扔出手中的纸牌..

　　然后按着纸牌上面的数找下一个被选中的小孩..

　　如果牌中的数是正数就顺时针数..

　　如果是负数就逆时针数..

　　

　　其中第 i 个被选中的小孩会得到f( i )颗糖..

　　f( i )表示 i 的正因子个数..

 

　　要求是找出得到糖最多的孩子个数..

　　

输入：　　

　　n k 表示有n个小孩..从第k个开始

　　接下来 n 行有n个小孩的名字和他手上的牌的编号..

 

思路：

　　一开始想的是暴力找出这个小孩..

　　但是会很麻烦..

　　然后这里就用到了反素数了..

　　反素数：<>

　　找出f[ j ] > f[ i ] ： f[ j ]为 j 的正因子个数..

　　然后就可以找出n之前正因子最多的那个数 即 得糖最多的那个小孩编号 ans..

　　再找出这个小孩是谁..

 

　　用线段树模拟找的过程..感觉跟二分有点像~感觉..

 

Tips：

　　※ 改的是 rt 是 sum 的..但是输入的per的数据是 l 和 r

　　※ 还有一个让我很纠结的就是根据数的正负向左数还是向右数..

 

Code：

1 #include 
      
        2 #include 
       
         3  4 const int MAXN = 500010; 5  6 struct P 7 { 8     char name[20]; 9     int sum;10 }per[MAXN];11 int sum[MAXN<<2];12 13 int antiprime[]={
    1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,14                  7560,10080,15120,20160,25200,27720,45360,50400,55440,83160,110880,15                  166320,221760,277200,332640,498960,554400,665280};16 int factorNum[]={
    1,2,3,4,6,8,9,10,12,16,18,20,24,30,32,36,40,48,60,64,72,80,84,90,96,17                  100,108,120,128,144,160,168,180,192,200,216,224};18 19 void pushup(int rt)20 {21     sum[rt] = sum[rt<<1] + sum[rt<<1|1];22 }23 24 void creat(int l, int r, int rt)25 {26     if(l == r) {27         scanf("%s %d", per[l].name, &per[l].sum);28         sum[rt] = 1;29         return;30     }31     int mid = (l+r)>>1;32     creat(l, mid, rt<<1);33     creat(mid+1, r, rt<<1|1);34     pushup(rt);35 36 }37 38 int modify(int k, int l, int r, int rt)39 {40     if(l == r) {41         sum[rt]--;42         return l;43     }44     int mid = (l+r)>>1;45     int loc;46     if(k <= sum[rt<<1]) loc = modify(k, l, mid, rt<<1);47     else loc = modify(k-sum[rt<<1], mid+1, r, rt<<1|1);48     pushup(rt);49     return loc;50 }51 52 int main()53 {54     int i, j;55     int n, k;56     int loc, tmp;57     int ans;58     while(scanf("%d %d", &n, &k) != EOF)59     {60         creat(1, n, 1);61 62         for(i = 0; i < 36; ++i) if(antiprime[i] <= n) ans = i;63 64         k = ((k-1)%n+n)%n+1;65         loc = modify(k, 1, n, 1);66 67         for(i = 1; i < antiprime[ans]; ++i) {68             if(per[loc].sum > 0) k = ((k+per[loc].sum - 2)%sum[1] + sum[1])%sum[1] + 1;69             else k = ((k+per[loc].sum-1)%sum[1] + sum[1])%sum[1] + 1;70             loc = modify(k, 1, n, 1);71         }72 73         printf("%s %d\n", per[loc].name, factorNum[ans]);74     }75     return 0;76 }
       
      

 

题目链接：