题目分析与解题方法

题意理解

这道题目描述了一个环形游戏，$N$ 个孩子围成一圈，每个孩子有一个名字和一个非零整数。游戏规则如下：

1. 从第 $K$ 个孩子开始
2. 当前孩子报出自己的数字 $A$ 后离开圆圈
3. 如果 $A$ 为正，则下一个离开的是左边第 $A$ 个孩子
4. 如果 $A$ 为负，则下一个离开的是右边第 $-A$ 个孩子
5. 第 $p$ 个离开的孩子获得 $F(p)$ 颗糖果，其中 $F(p)$ 是能整除 $p$ 的正整数个数
6. 找出获得糖果最多的孩子

解题方法

核心思路

1. 反素数应用：使用反素数表快速找到不超过 $N$ 的最大反素数 $R$，因为反素数对应的 $F(p)$ 值最大
2. 线段树模拟：使用线段树高效维护当前圆圈中的孩子位置，支持快速查询和删除操作
3. 约瑟夫环变种：处理环形结构中的删除顺序问题

关键步骤

1. 预处理反素数表 $RPrime$ 和对应的约数个数表 $fact$
2. 建立线段树维护当前圆圈中的孩子
3. 模拟游戏过程，计算第 $R$ 个离开的孩子（$R$ 是最大的不超过 $N$ 的反素数）
4. 输出该孩子的名字和 $F(R)$ 值

复杂度分析

• 时间复杂度：$O(N\log N)$（线段树操作）
• 空间复杂度：$O(N)$

标准代码

#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
#define MAXN 500005
int RPrime[]= //反素数
{
    1,2,4,6,12,24,36,48,60,120,180,240,360,720,840,1260,1680,2520,5040,7560,10080,15120,
    20160,25200,27720,45360,50400,55440,83160,110880,166320,221760,277200,332640,498960,
    554400
};
 
int fact[]= //反素数约数个数
{
    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,100,108,120,128,
    144,160,168,180,192,200,216
};
struct A
{
    char s[15];
    int num;
}a[MAXN];
int n,k,sum[4*MAXN];
void pushup(int root)
{
    sum[root] = sum[2*root] + sum[2*root+1];
}
void build(int l,int r,int root)
{
    if(l == r)
    {
        sum[root] = 1;
        return ;
    }
    int mid = (l+r)/2;
    build(l,mid,2*root);
    build(mid+1,r,2*root+1);
    pushup(root);
}
int update(int l ,int r,int root,int k)
{
    sum[root]--;
    if(l == r)
        return l;
    int mid = (l+r)/2;
    if(k <= sum[2*root]) update(l,mid,2*root,k);
    else update(mid+1,r,2*root+1,k-sum[2*root]);
}
int main()
{
    while(cin>>n>>k)
    {
        int i,p;
        for(i = 1; i <= n; i++)
        {
            scanf(" %s%d",a[i].s,&a[i].num);
        }
        i = 0;
        while(RPrime[i] <= n)//找到最大的反素数
        {
            i++;
        }
        p = i-1;
        build(1,n,1);
        int tmp = 0;//tmp 表示当前位子
        a[tmp].num = 0;
        for(i = 1; i <= RPrime[p]; i++)
        {
            int mod = sum[1];//mod 表示当前圈子中的全部人数
            if(a[tmp].num > 0)
                k = ((k + a[tmp].num - 2)%mod + mod)%mod + 1;//k 表示第几个人要出去
            else//因为k  是从1 开始的，为了避免k + a[tmp] == 0 的情况，所以要在后面+1，前面-1
                k = ((k + a[tmp].num - 1)%mod + mod)%mod + 1;
            tmp = update(1,n,1,k);//tmp 表示第k 个出去的人的当前位子
        }
        printf("%s %d\n",a[tmp].s,fact[p]);
    }
}