Toxic Pepperoni

· · 题解

对于第一问：设全集为 U，所要求的东西为

\begin{aligned}& \sum_{S\subseteq U,|S|=k}[\gcd\{S\}=1]\\=& \sum_{S\subseteq U,|S|=k}\sum_{d|\gcd\{S\}}\mu(d)\\=& \sum_{d}\mu(d)\dbinom{g_d}{k}\end{aligned}

其中 g_d 为 a 中能被 d 整除的数字个数。使用 Dirichlet 后缀和即可求出 g 数组。

观察到 g 数组中元素和的上界不超过 nw^{\frac{1}{3}}，w 为值域。这启发我们对于每个枚举到的 d，暴力对所有 k\le g_d 计算贡献。至此我们做完了第一问。

对于第二问：所要求的东西为

& \sum_dd\sum_{S\subseteq U,|S|=k}[\gcd\{S\}=d]\\ =& \sum_dd\sum_{S\subseteq U,|S|=k}\sum_{bd|\gcd\{S\}}\mu(b)\\ =& \sum_dd\sum_{b}\mu(b)\dbinom{g_{bd}}{k}\\ =& \sum_dd\sum_{T}\mu(\dfrac{T}{d})\dbinom{g_{T}}{k} \end{aligned}

对于某个特定的 T，枚举 d 算前一半，枚举 k 算后一半，拼起来就做完了第二问。

#include"bits/stdc++.h"
using namespace std;
const int maxn = 1000100;
namespace fastio {
    const int MAXBUF = 1 << 23;
    char buf[MAXBUF], *p1 = buf, *p2 = buf;
    char pbuf[MAXBUF], *pp = pbuf;
    inline char getc() { return (p1 == p2) && (p2 = (p1 = buf) + fread(buf, 1, MAXBUF, stdin)), p1 == p2 ? EOF : *p1++; }
    inline void putc(char c) { (pp == pbuf + MAXBUF) && (fwrite(pbuf, 1, MAXBUF, stdout), pp = pbuf), *pp++ = c; }
    inline void print_final() { fwrite(pbuf, 1, pp - pbuf, stdout), pp = pbuf; }
}
#ifndef LocalTest
    using fastio::getc;
    using fastio::putc;
    using fastio::print_final;
#else
    #define getc getchar
    #define putc putchar
    void print_final(){}
#endif
template <class _Tp>inline _Tp& read(_Tp& x) {
    bool sign = 0;
    char ch = getc();
    for (; !isdigit(ch); ch = getc()) sign |= (ch == '-');
    for (x = 0; isdigit(ch); ch = getc()) x = x * 10 + (ch ^ 48);
    return sign ? (x = -x) : x;
}
template <class _Tp>inline void write(_Tp x) {
    if (x < 0) putc('-'), x = -x;
    if (x > 9) write(x / 10);
    putc((x % 10) ^ 48);
}
template <typename _Tp,typename ...Args>inline void write(_Tp x,Args ...args){
    write(x),putc(' '),write(args...);
}
template<typename _Tp,typename ...Args>inline bool read(_Tp& x,Args& ...args) {
    return read(x)&&read(args...);
}
int n,m,w,mo;
int a[maxn],g[maxn];
int pw[maxn],ip[maxn];
inline int ksm(int b,int t){
    int ret=1;
    while(t){
        if(t&1)ret=1ll*ret*b%mo;
        b=1ll*b*b%mo,t>>=1;
    }
    return ret;
}
inline int inv(int x){
    return ksm(x,mo-2);
}
inline int C(int u,int d){
    return (1ll*pw[u]*ip[d]%mo)*ip[u-d]%mo;
}
int v[maxn],mu[maxn],Bw[maxn],ans[maxn],ans2[maxn];
int p[maxn],Top;
int main(){
    read(n),read(m),read(mo);
    for(int i=1;i<=n;i++)
        read(a[i]),g[a[i]]++,w=max(w,a[i]+1);
    pw[0]=ip[0]=1;
    for(int i=1;i<=n;i++)
        pw[i]=1ll*i*pw[i-1]%mo;
    ip[n]=inv(pw[n]);
    for(int i=n;i>=2;i--)
        ip[i-1]=1ll*i*ip[i]%mo;
    mu[1]=1;
    for(int i=2;i<=w;i++){
        if(v[i]==0)mu[i]=-1,p[Top++]=i;
        for(int j=0;j<Top&&i*p[j]<=w;j++){
            v[i*p[j]]=1;
            if(i%p[j]==0)break;
            mu[i*p[j]]=-mu[i];
        }
    }
    for(int i=0;i<Top;i++)
        for(int j=w/p[i];j>=1;j--)
            g[j]+=g[j*p[i]];
    for(int i=1;i<=w;i++)
        for(int j=i;j<=w;j+=i)
            Bw[j]=(Bw[j]+1ll*i*(mo+mu[j/i]))%mo;
    for(int i=1;i<=w;i++){
        for(int j=1;j<=g[i];j++){
            int o=C(g[i],j);
            ans[j]=(ans[j]+1ll*o*(mo+mu[i]))%mo;
            ans2[j]=(ans2[j]+1ll*o*Bw[i])%mo;
        }
    }
    for(int i=1,k;i<=m;i++){
        read(k);
        write(ans[k]),putc(' '),write(ans2[k]),putc('\n');
    }
    print_final();
}