自动搬运

查看原文

来自洛谷，原作者为

	maojun 猫君

搬运于2025-08-24 23:00:03，当前版本为作者最后更新于2024-06-30 10:25:00，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

upd 2024.7.24 有点详略不当，被骂了。

---

显然有 $f(0)=0,f(1)=1$。

把 $(1+\sqrt 2)^n$ 展开，可以得到 $f(n)=2f(n-1)+f(n-2)$

这样就可以 $O(n)$ 递推出 $f$。

---

看看怎么更好地表示 $g$。

记全集 $U=\{1,2,\dots,n\}$。

引理： 如果 $f(0)=0,f(1)=1,f(n)=af(n-1)+bf(n-2)$，且 $\gcd(a,b)=1$，则 $\gcd(f(x),f(y))=f(\gcd(x,y))$。

证明：

先证：$f_{n+m}=f_{n+1}f_m+bf_nf_{m-1}$。

考虑 $\begin{bmatrix}f_{n+1}&f_n\end{bmatrix}=\begin{bmatrix}a&1\\b&0\end{bmatrix}\begin{bmatrix}f_n&f_{n-1}\end{bmatrix}$，$\begin{bmatrix}f_1&f_0\end{bmatrix}=\begin{bmatrix}1&0\end{bmatrix}$。

注意到 $\begin{bmatrix}a&1\\b&0\end{bmatrix}=\begin{bmatrix}f_2&f_1\\bf_1&bf_0\end{bmatrix}$，应当有 $\begin{bmatrix}a&1\\b&0\end{bmatrix}^n=\begin{bmatrix}f_{n+1}&f_n\\bf_n&bf_{n-1}\end{bmatrix}$，归纳一下可以发现是对的。

则有：

$$\begin{aligned}\begin{bmatrix}f_{n+m+1}&f_{n+m}\end{bmatrix}&=\begin{bmatrix}a&1\\b&0\end{bmatrix}^m\begin{bmatrix}f_{n+1}&f_n\end{bmatrix}\\&=\begin{bmatrix}f_{m+1}&f_m\\bf_m&bf_{m-1}\end{bmatrix}\begin{bmatrix}f_{n+1}&f_n\end{bmatrix}\\&=\begin{bmatrix}f_{n+1}f_{m+1}+bf_mf_n&f_{n+1}f_m+bf_nf_{m-1}\end{bmatrix}\end{aligned} $$

回到原命题。

考虑 $\gcd(f_{n+m},f_n)=\gcd(f_{n+1}f_m+bf_nf_{m-1},f_n)=\gcd(f_{n+1}f_m,f_n)$。

显然有 $\gcd(f_1,f_2)=1$，结合 $\gcd(a,b)=1$ 可归纳得到 $\gcd(f_{n+1},f_n)=1$。

于是有 $\gcd(f_{n+m},f_n)=\gcd(f_m,f_n)$，根据辗转相除有 $\gcd(f_{n+m},f_n)=\gcd(f_{\gcd(n+m,n)},f_0)=f_{\gcd(n+m,n)}$。

即 $\gcd(f(x),f(y))=f(\gcd(x,y))$。

这样有 $\gcd\limits_{i\in T}f(i)=f(\gcd(T))$。看起来非常友好。

但是现在 $g$ 是 $\operatorname{lcm}$ 相关的东西，所以我们考虑用点什么东西把它和子集 $\gcd$ 建立联系。

引理：$\operatorname{lcm}(S)=\prod\limits_{T\subseteq S}\gcd(T)^{(-1)^{|T|-1}}$

证明：

注意到 $\operatorname{lcm}$ 这个东西相当于对于每个质因数在次数上取 $\max$，$\gcd$ 相当于取 $\min$。

根据 $\min-\max$ 容斥，有：$\max(S)=\sum\limits_{T\subseteq S}\min(T)(-1)^{|T|-1}$。

记 $\operatorname{cnt}_{i,p}$ 为 $i$ 有多少个质因数 $p$。于是有：

$$\begin{aligned}\operatorname{lcm}(S)&=\prod\limits_pp^{\max\limits_{i\in S}\operatorname{cnt}_{i,p}}\\&=\prod\limits_pp^{\sum\limits_{T\subseteq S}\min\limits_{i\in T}\operatorname{cnt}_{i,p}(-1)^{|T|-1}}\\&=\prod\limits_{T\subseteq S}(\prod\limits_pp^{\min\limits_{i\in T}\operatorname{cnt}_{i,p}})^{(-1)^{|T|-1}}\\&=\prod\limits_{T\subseteq S}\gcd(T)^{(-1)^{|T|-1}}\end{aligned} $$

所以：

$$\begin{aligned} g(n)&=\prod\limits_{T\subseteq U}(\gcd\limits_{i\in T}f(i))^{(-1)^{|T|-1}}\\ &=\prod\limits_{T\subseteq U}f(\gcd(T))^{(-1)^{|T|-1}} \end{aligned} $$

注意，这里的 $\gcd(T)$ 是定义在非空集合上的。所以以上的枚举有一个隐含的 $T$ 非空的条件。

---

考虑怎么快速求。

$$\begin{aligned} g(n)&=\prod\limits_{T\subseteq U}f(\gcd(T))^{(-1)^{|T|-1}}\\ &=\prod\limits_{i=1}^nf(i)^{\sum\limits_{T\subseteq U}[\gcd(T)=i](-1)^{|T|-1}} \end{aligned} $$

记 $a(i)=\sum\limits_{T\subseteq U}[\gcd(T)=i](-1)^{|T|-1},A(i)=\sum\limits_{i\mid d}a(d)$，定义域都是 $U$。

引理：$A(i)=1$

证明：

记 $S_i=\{1,2,\dots,\left\lfloor\dfrac ni\right\rfloor\}$。

则 $A(i)=\sum\limits_{T\subseteq U}[i\mid\gcd(T)](-1)^{|T|-1}=\sum\limits_{T\subseteq S_i,T\ne\varnothing}{(-1)^{|T|-1}}$。

考虑 $\sum\limits_{T\subseteq S}(-1)^{|T|}=\sum\limits_{i=0}^{|S|}{|S|\choose i}(-1)^i=(1-1)^{|S|}=[|S|=0]$。

由于 $i\le n$，有 $|S_i|\ne0$。

于是：

$$\begin{aligned}A(i)&=\sum\limits_{T\subseteq S_i,T\ne\varnothing}{(-1)^{|T|-1}}\\&=-\sum\limits_{T\subseteq S_i,T\ne\varnothing}{(-1)^{|T|}}\\&=-(\sum\limits_{T\subseteq S_i}{(-1)^{|T|}}-(-1)^{|\varnothing|})\\&=-(0-1)=1\end{aligned} $$

那么由莫比乌斯反演，有 $a(i)=\sum\limits_{i\mid d}\mu(\dfrac di)A(d)=\sum\limits_{i\mid d}\mu(\dfrac di)$。

直接暴力求每个 $g$ 还是不太好，可以再带回去推一推。

$$\begin{aligned} g(n)&=\prod\limits_{i=1}^nf(i)^{\sum\limits_{T\subseteq U}[\gcd(T)=i](-1)^{|T|-1}}\\ &=\prod\limits_{i=1}^nf(i)^{\sum\limits_{i\mid d}\mu(\frac di)}\\ &=\prod\limits_{d=1}^n\prod\limits_{i\mid d}f(i)^{\mu(\frac di)} \end{aligned} $$

最后的式子出奇的简单。$O(n\ln n)$ 求 $s(d)=\prod\limits_{i\mid d}f(i)^{\mu(\frac di)}$ 即可，$g$ 就是 $s$ 的前缀积。

总复杂度 $O(\sum n\ln n)$，可过。

typedef long long ll;
const int N=1e6+5;
int mu[N];
inline ll inv(ll x,int p){ll r=1;for(int y=p-2;y;y>>=1,x=x*x%p)if(y&1)r=r*x%p;return r;}

ll f[N],s[N];
int main(){
	mu[1]=1;
	for(int i=1;i<N;i++)
		for(int j=i+i;j<N;j+=i)
			mu[j]-=mu[i];
	int T;scanf("%d",&T);
	for(int n,p;T--;){
		scanf("%d%d",&n,&p);
		f[1]=1;
		for(int i=2;i<=n;i++)f[i]=(2*f[i-1]+f[i-2])%p;
		fill(s+1,s+n+1,1);
		for(int i=1;i<=n;i++){
			ll x=f[i],y=inv(x,p);
			for(int j=i;j<=n;j+=i)
				if(mu[j/i]==1)s[j]=s[j]*x%p;
				else if(mu[j/i])s[j]=s[j]*y%p;
		}
		ll res=0,g=1;
		for(int i=1;i<=n;i++){
			g=g*s[i]%p;
			res=(res+g*i)%p;
		}
		printf("%lld\n",res);
	}
	return 0;
}