自动搬运

查看原文

来自洛谷，原作者为

	iostream Think three times, code twice and take the first place.

搬运于2025-08-24 22:18:27，当前版本为作者最后更新于2020-03-11 13:43:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

出题人来发一下官方题解qwq

题意

定义数列 $a_1=1,a_2=2,a_n=2a_{n-1}-ka_{n-2}$。

已知对于 $n$ 以内只有 $m$ 个给定的质数不满足 $p\mid a_p$ ，其他质数均满足。

求最小可能的 $k$。取模 ntt 模数 $c$。

$n\le 3\times 10^8,m\le 20$

可以做 $n\le 10^9,m\le 20$

2s

Sol

首先考虑答案是什么：

方法1：数学推导

算出通项为 $a_n={(1+\sqrt {k+1})^n-(1-\sqrt {k+1})^n\over 2\sqrt {k+1}}$。

用二项式定理展开通项可以得到 $a_p=\sum_{i=0}^{p-1\over 2} {p \choose 2i+1} (k+1)^i$。

由于 $p$ 是质数然后有 $p\choose i$ 仅当 $i=0$ 或 $i=p$ 时为1，否则等于0。

$a_p=(k+1)^{p-1\over 2} \pmod p$

当且仅当 $k\equiv -1 \pmod p$ 时 $p\mid a_p$。

根据中国剩余定理，可以解出最小的 $k$ 等于 $p_1p_2\dots p_m-1$，$p_i$ 是所有满足 $p_i|a_{p_i}$ 的奇质数。

那么题意是求质数前缀积，除去其中若干个质数。

方法二：打表找规律

结论与上述相同。

部分分

略

一个简单的 std 做法，不用卡常

依然压位保存质数表，考虑使用埃氏筛法，首先去掉 3 的倍数和所有偶数；

枚举 $p=-1 \pmod 6$ 的质数，筛去形如 $p^2+6kp$ 以及 $p^2+(6k+2)p$ 的合数。

枚举 $p=1 \pmod 6$ 的质数，筛去形如 $p^2+6kp$ 以及 $p^2+(6k+4)p$ 的合数。

然后还有枚举的 $p$ 应该是在 $\sqrt n$ 以内的。

最后可以遍历一遍所有质数乘起来，这个不是时间瓶颈。

直接写应该就可以通过，时间复杂度 $O(n\log\log n)$ 常数大概 $1\over 18$。

参考代码：

int n,m,q,a[233],mod,ans=1;

struct bitst {
	uint64_t buf[301000000/64/2+1];
	bool operator[](const int&x)
	{ return buf[x>>6]>>(x&63)&1; }
	void set(const int&x)
	{ buf[x>>6]|=1ull<<(x&63); }
}v;

void solve()
{
	scanf("%d%d%d",&n,&q,&mod);
	for(int i=0; i<q; i++){
		scanf("%d",a+i),--a[i];
		if(!a[i])return puts("-1")*0;
	}
	sort(a,a+q);
	q=unique(a,a+q)-a;
	v.set(0);
	for(int i=9; i<=n; i+=6)
		v.set(i>>1);
	m=n>>1;
	for(int i=2,j=3; (2*i+1)*(2*i+1)<=n; i+=3,j+=3)
	{
		if(!v[i])
		{
			for(int k=6*i+3,x=i*(i+1)*2,y=x+i*2+1; x<=m; x+=k,y+=k)
				v.set(x),v.set(y);
		}
		if(!v[j])
		{
			for(int k=6*j+3,x=j*(j+1)*2,y=x+j*4+2; x<=m; x+=k,y+=k)
				v.set(x),v.set(y);
		}
	}
	int L=n/2/64,now=0,j=0;
	for(int i=0; i<L; i++)
	for(uint64_t s=~v.buf[i]; s; s&=s-1)
	{
		int p=(__builtin_ctzll(s)+(i<<6))<<1|1;
		for(++now; j<q&&a[j]<now; ++j);
		if(a[j]!=now)ans=1ll*ans*p%mod;
	}
	for(uint64_t s=~v.buf[L]; s; s&=s-1)
	{
		int p=(__builtin_ctzll(s)+(L<<6))<<1|1;
		if(p>n)break;
		for(++now; j<q&&a[j]<now; ++j);
		if(a[j]!=now)ans=1ll*ans*p%mod;
	}
	printf("%d",ans-1);
}

正经的做法（与比赛题无关，$n \le 10^9$）

求质数前缀积可以用类似 min-25 筛的做法，需要先求出根号个 $\lfloor \frac n i \rfloor$ 处的阶乘，然后枚举最小质因子 $p$ 作除法。

计算阶乘可以用分块+倍增的方法计算，复杂度 $O(\sqrt n\log n)$ ，需要加记忆化。

min-25筛的时候还需要记录素数个数，然后要除去这么多个 $p$ 的因子。

时间复杂度大概是 $O(n^{0.75})$。空间 $O(n^{0.5})$。

然后还有一个问题是求第 k 个质数，显然可以二分+min-25筛，

还有一种更简单的方法，是分段打表+区间筛法，预处理 $i\times 10^6$ 的位置的质数个数，求第 k 个质数定位到某个合法区间以后跑区间筛法求即可。

min-25筛部分的参考代码（感谢 rushcheyo）：

int solve()
{
	for (int i = m; i; --i)
		f[i] = fact(val[i]);
	for (int j = 1; j <= p[0]; ++j) {
		static int tmp_pw[30];
		tmp_pw[0] = invp[j];
		for (int i = 1; i < 30; ++i) tmp_pw[i] = 1ll * tmp_pw[i - 1] * tmp_pw[i - 1] % P;
		for (int i = 1, k, lstk = -1, lstval = -1; i <= m && p[j] * p[j] <= val[i]; ++i) {
			k = val[i] / p[j] <= BB ? id1[val[i] / p[j]] : id2[n / (val[i] / p[j])];
			int tmp = g[k] - (j - 1);
			g[i] -= tmp;
			if (k != lstk) {
				lstval = 1ll * pro[j - 1] * getinv(f[k]) % P;
				for (; tmp; tmp &= tmp - 1) lstval = 1ll * lstval * tmp_pw[__builtin_ctz(tmp)] % P;
				lstk = k;
			}
			f[i] = 1ll * f[i] * lstval % P;
		}
	}
	return 1ll * getinv(2) * (f[1] + P) % P;
}

代码得到 $[1,n]$ 的奇素数积。

预处理阶乘的部分参见 P5282 快速阶乘算法。