「DROI」Round 1 游戏题解

Demeanor_Roy · 2023-01-02 18:59:08 · 题解

出题人题解。

首先发觉 n 的范围过大导致无论从哪个方向攻破都难有进展，不难想到缩小 n 的范围。

令 \pi(n) 表示小于等于 n 的质数个数，则有结论：若 \pi(n) > Q，小朋友必败。让我们考虑证明这个结论。

考虑质数 p ，令 k 是使 p^k \leq n 的最大正整数，显然若所选 x 中 p 的指数为 k ，则必须存在一个 a_i 使得 a_i 中 p 的指数等于 k 才能唯一确定 x 中 p 的指数。所以若存在一个质数 p，使得所有 a_i 中 p 指数的最大值小于 k ，那么我们就可以选择 p^k 作为 x ，小朋友必败。
而对于任意两个不同质数 p，q，显然都有 p^{k1} \times q^{k2} > n，所以一个 a_i 最多能使小朋友确定 x 中一个质数的指数。据此可知，Q 次提问最多能确定 Q 个质数的指数。显然当 \pi(n) > Q时，小朋友必然无法猜出 x 的值，直接输出game won't stop即可。

于是我们接下来只需要考虑 \pi(n) \leq Q 的情况。

先给出结论：当且仅当对于所有质数 p \in [1,n]，都有 p^k 或其倍数在 a_i 中出现过时，小朋友能唯一确定 x。给出证明：

充分性：根据以上条件，小朋友一定能确定每个质数在 x 中的指数，故能唯一确定 x。
必要性：设质数 p 不满足上述条件，不妨令 x=p^k，则小朋友无法唯一确定 x。

于是对于所有质数 p \in [1,n] 求出 p^k 或其倍数首次出现的位置，取 max 即为答案。线性筛预处理出一些信息，实现精细单次询问时间复杂度可做到 O(Q)。我写代码时偷懒有一个小常数，但无伤大雅。

这里顺便阐明一下部分分依据：

第一档部分分是给 n^2Q 暴力的，只要稍加思考过这档不难。
第二档部分分是给没有推出缩小 n 的范围但发掘了一些其他性质的。
第三档部分分是给所有性质都推出来，但不会线性筛或者常数实在太大的人。

至此本题解决完毕。下附代码：

#include<bits/stdc++.h>
using namespace std;
#define LL long long
const int N=3.3e7+10,M=2e6+10;
LL n,A[M];
int T,m,id,v[N],sum[N],prime[M<<1];
bool ispk[N],check[N];
inline LL read()
{
    LL x=0;char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x;
}
inline void Euler()
{
    v[1]=ispk[1]=true;
    for(int i=2;i<N;i++)
    {
        if(!v[i]) v[i]=i,prime[++id]=i,ispk[i]=true;
        for(int j=1;j<=id;j++)
        {
            if(i*prime[j]>=N||v[i]<prime[j]) break;
            v[i*prime[j]]=prime[j];
            ispk[i*prime[j]]=(ispk[i]&&(v[i]==prime[j]));
        }
        sum[i]=sum[i-1]+(v[i]==i);
    }
}
inline void solve()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)   A[i]=read();
    if(prime[m+1]<=n) return printf("game won't stop\n"),void();
    for(int i=1;i<=m;i++)   check[prime[i]]=false;
    int now=0;
    for(int i=1;i<=m;i++)
    {
        while(A[i]*A[i]>n&&!ispk[A[i]])     A[i]/=v[A[i]];
        if(A[i]*v[A[i]]>n) 
        {
            now+=!check[v[A[i]]];
            check[v[A[i]]]=true;
        }
        if(now==sum[n]) 
        {
            printf("%d\n",i);
            break;
        }
        else if(m-i+now<sum[n]) 
        {
            printf("game won't stop\n");    
            break;
        }
    }
}
int main()
{   
    Euler();
    scanf("%d",&T);
    while(T--)  solve();
    return 0;   
}

「DROI」Round 1 游戏 题解

「DROI」Round 1 游戏题解