自动搬运

查看原文

来自洛谷，原作者为

	Undead2008 。

搬运于2025-08-24 22:56:21，当前版本为作者最后更新于2024-03-23 16:02:56，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

对于第一问：设全集为 $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$ 计算贡献。至此我们做完了第一问。

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

$$\begin{aligned} & \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();
}