「BZOJ4833」最小公倍佩尔数

题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=4833。

巧妙的构造

首先根据特征根或者打表可以知道：

$$f_n= \begin{cases} 0&n=0\\ 1&n=1\\ 2f_{n-1}+f_{n-2}&{\rm otherwise} \end{cases}$$

那么这个东西的性质其实和斐波那契数列是一样的，所以很容易得到：

$$\gcd(f_i,f_j)=f_{\gcd(i,j)}$$

有一个$\rm min-max$容斥的拓展是这样的：

$${\rm lcm} (S)=\prod_{T\subseteq S,T\ne \phi}\gcd(T)^{(-1)^{|T|-1}}$$

考虑每个质因数就可以知道这个东西和$\rm min-max$容斥等价。

那么容易得到：

$$g(i)=\prod_{T\subseteq S}f(\gcd(T))^{(-1)^{|T|-1}}$$

很容易想到枚举$\gcd$的答案然后套莫比乌斯反演，但是这样很不好搞。

注意到这样的瓶颈是，如果我们枚举答案，那么我们就要算$\gcd$恰好等于$x$的贡献，如果我们能通过一种方法搞成，$x|\gcd$的集合都有贡献就好搞了，考虑构造：

$$f_i=\prod_{d|i}h_d$$

显然$h$可以很快的算出来的，因为我们知道$f$，所以$g$可以写成：

$$g(i)=\prod_{d=1}^{i}h_d^{\sum_{T\subseteq S,T\ne \phi}[d|\gcd(T)](-1)^{|T|-1}}$$

注意到假设我们硬点一个$d$的倍数$x$，那么其他$d$的倍数的子集$s$和$s\cup x$会两两抵消，所以指数最后会剩下个$1$，那么：

$$g(i)=\prod_{d=1}^{i}h_d$$

复杂度$O(n\log n)$。

#include<bits/stdc++.h>
using namespace std;

void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}

void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}

#define lf double
#define ll long long 

#define pii pair<int,int >
#define vec vector<int >

#define pb push_back
#define mp make_pair
#define fr first
#define sc second

#define data asd09123jdf02i3h

#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)

const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;

int n,mod,f[maxn];

int qpow(int a,int x) {
    int res=1;
    for(;x;x>>=1,a=1ll*a*a%mod) if(x&1) res=1ll*res*a%mod;
    return res;
}

void solve() {
    read(n),read(mod);
    f[0]=0,f[1]=1;
    for(int i=2;i<=n;i++) f[i]=(2ll*f[i-1]+f[i-2])%mod;
    for(int i=1;i<=n;i++) {
        int t=qpow(f[i],mod-2);
        for(int j=i+i;j<=n;j+=i)
            f[j]=1ll*f[j]*t%mod;
    }
    f[0]=1;
    for(int i=1;i<=n;i++) f[i]=1ll*f[i-1]*f[i]%mod;
    int ans=0;
    for(int i=1;i<=n;i++) ans=(ans+1ll*f[i]*i%mod)%mod;
    write(ans);
}

int main() {
    int t;read(t);
    while(t--) solve();
    return 0;
}