https://www.luogu.com.cn/problem/P6197
毒瘤题，还卡常qwq.......
给一个长度为\(n\)的数列\(a\)，满足递推关系\(a_n=2a_{n-1}+ka_{n-2}\)（\(k\)是你指定的值），边界\(a_1=1,a_2=2\)。
然后在给出\(m\)个质数，求最小的\(k\)使得对于在\(1\cdots n\)内且不在指定的数内的素数\(p\)，都有\(p\mid a_p\)，对一个\(NTT\)模数\(c\)取模。
你看它递推式长得那么别致就知道肯定有用 但NTT模数就很迷惑
于是大力推通项
先假设\(a_n=q^n\)，首先要满足
\[q^n-2q^{n-1}-kq^{n-2}=0\]
提个\(q^{n-2}\)出来
\[q^{n-2}(q^{2}-2q-k)=0\]
及\(q^2-2q-k=0\)，解方程得到
\[q_0=\frac{2+\sqrt{4+4k}}{2}=1+\sqrt{k+1}\]
\[q_1=1-\sqrt{k+1}\]
然后找\(c_0,c_1\)满足\(c_0q_0+c_1q_1=a_1=1,c_0q_0^2+c_1q_1^2=a_2=2\)
解得
\[c_1=\frac{1}{2\sqrt{k+1}},c_2=\frac{-1}{2\sqrt{k+1}}\]
通项即为\(a_n=c_0q_0^n+c_1q_1^n=\frac{(1+\sqrt{k+1})^n-(1-\sqrt{k+1})^n}{2\sqrt{k+1}}\)，下面令\(r=\sqrt{k+1}\)
\[a_n=\frac{(1+r)^n-(1-r)^n}{2r}\]
注意到分母，用二项式定理展开
\[\sum\limits_{i=0}^n \binom{n}{i} r^i-\sum\limits_{i=0}^n (-1)^i\binom{n}{i}r^i\]
发现偶数项全部蒸发了，即
\[2\sum\limits_{2i+1 \le n} \binom{n}{2i+1}r^{2i+1}\]
把分母去掉
\[a_n=\sum\limits_{2i+1 \le n} \binom{n}{2i+1} r^{2i}=\sum\limits_{2i+1\le n} \binom{n}{2i+1} (k+1)^i\]
太神奇辣
而我们仅要求\(p \mid a_p\)，其中\(p\)是一个质数，有注意到\(\binom{p}{i}=\frac{p!}{i!(p-i)!}\)，分母与\(p\)互质，讲除法转换成乘逆元，分子又有因数\(p\)，所以当\(0<i<p\)时\(p\mid \binom{p}{i}\)（需要特判\(\binom{p}{0}=\binom{p}{p}=1\)）。
我们只关心大于\(2\)的质数\(p\)（\(a_2=2\)显然\(2 \mid a_2\)），所以
\[a_p=\sum\limits_{i=0}^{(p-1)/2} \binom{p}{2i+1}(k+1)^i \equiv (k+1)^p \pmod p\]
所以我们只要求一个\(k\)满足对于不在指定的数中的素数，都有\(k+1 \equiv 0 \pmod p\)，由于质数两两互质，由中国剩余定理可得最小的\(k=\prod p - 1\)（\(p\)没有被指定且\(1\le p \le n\)）。
于是线性筛出\(1...n\)内的素数算上面那个东西就好了。
无解的情况就是指定的素数中有\(2\)的时候（与题目里不同，题目中是指定第\(i\)大的质数）。
但这题非常毒瘤...还要卡常.....
并不会一些奇怪的筛法...这里就提一下普通的线性筛如何卡常吧qwq...
建议不要用vector，vector就算开了c++11和O2还是慢.....
所以尽量用数组，另外bitset也不用了...bool数组挺快的感觉...
还有可以特判一下当前遍历到的数\(i\)是\(2\)的倍数的时候..
再写一写循环展开啥的...火车头也加上好了...
如果还卡不过就洗洗睡吧多交几次试试...
实在卡不过也没办法了...写出题人那种埃氏筛吧qwq
代码太丑就不放了qwq
原文：https://www.cnblogs.com/wxq1229/p/12509119.html