题解：P10663 BZOJ4833 最小公倍佩尔数

_maojun_ · 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}

所以：

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

考虑怎么快速求。

记 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 还是不太好，可以再带回去推一推。

最后的式子出奇的简单。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;
}