题解 P6197 【[EER1]礼物】

· · 题解

出题人来发一下官方题解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 快速阶乘算法。