自动搬运

查看原文

来自洛谷，原作者为

	Demeanor_Roy 小时候我们总想去改变别人，后来发现，比起改变，筛选是性价比更高的事。

搬运于2025-08-24 22:44:17，当前版本为作者最后更新于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)$。我写代码时偷懒有一个小常数，但无伤大雅。

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

1. 第一档部分分是给 $n^2Q$ 暴力的，只要稍加思考过这档不难。

2. 第二档部分分是给没有推出缩小 $n$ 的范围但发掘了一些其他性质的。

3. 第三档部分分是给所有性质都推出来，但不会线性筛或者常数实在太大的人。

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

#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;	
}