BZOJ4833: [Lydsy1704月賽]最小公倍佩爾數（min-max容斥）

傳送門

題解：

fn=2fn−1+fn−2 f n = 2 f n − 1 + f n − 2

有一個結論是形如 fn=afn−1+bfn−2 f n = a f n − 1 + b f n − 2 ，有 gcd{fx,fy}=fgcd{x,y} gcd { f x , f y } = f gcd { x , y } 。

利用 min−max m i n − m a x 容斥，有：

lcmfT=∏S∈Tf(−1)|S|+1gcd{S} lcm f T = ∏ S ∈ T f gcd { S } ( − 1 ) | S | + 1

令

∏d|ngd=fn ∏ d | n g d = f n

那麼 lcmf{T}===∏S∈Tf(−1)|S|+1gcd{S}∏S∈T(∏d|gcd{S}gd)(−1)|S|+1∏dg∑S∈T,d|gcd{S}(−1)|S|+1d lcm f { T } = ∏ S ∈ T f gcd { S } ( − 1 ) | S | + 1 = ∏ S ∈ T ( ∏ d | gcd { S } g d ) ( − 1 ) | S | + 1 = ∏ d g d ∑ S ∈ T , d | gcd { S } ( − 1 ) | S | + 1

發現 gd g d 對大等于 d d <script type="math/tex" id="MathJax-Element-639">d</script>的項都會産生貢獻，我們反演之後掃一遍即可。

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

const int RLEN=<<|;
inline char nc() {
    static char ibuf[RLEN],*ib,*ob;
    (ib==ob) && (ob=(ib=ibuf)+fread(ibuf,,RLEN,stdin));
    return (ib==ob) ? - : *ib++;
}
inline int rd() {
    char ch=nc(); int i=,f=;
    while(!isdigit(ch)) {if(ch=='-')f=-; ch=nc();}
    while(isdigit(ch)) {i=(i<<)+(i<<)+ch-'0'; ch=nc(); }
    return i*f;
}
inline void W(int x) {
    static int buf[];
    if(!x) {putchar('0'); return;}
    if(x<) {putchar('-'); x=-x;}
    while(x) {buf[++buf[]]=x%; x/=;}
    while(buf[]) {putchar(buf[buf[]--]+'0');}
}

const int N=+; int mod;
inline int add(int x,int y) {return (x+y>=mod) ? (x+y-mod) : (x+y);}
inline int dec(int x,int y) {return (x-y<) ? (x-y+mod) : (x-y);}
inline int mul(int x,int y) {return (long long)x*y%mod;}
inline int power(int a,int b,int rs=) {for(;b;b>>=,a=mul(a,a)) if(b&) rs=mul(rs,a); return rs;}

int n,f[N],g[N]; 
inline void solve() {
    n=rd(), mod=rd();
    f[]=; f[]=; 
    for(int i=;i<=n;i++) g[i]=;
    for(int i=;i<=n;i++) f[i]=add(mul(,f[i-]),f[i-]);
    for(int i=;i<=n;i++) {
        g[i]=mul(f[i],power(g[i],mod-));
        for(int j=i+i;j<=n;j+=i) g[j]=mul(g[j],g[i]);
    } 
    int ans=;
    for(int i=;i<=n;i++) {
        ans=add(ans,mul(g[i],i));
        g[i+]=mul(g[i+],g[i]);
    } W(ans), putchar('\n');
}
int main() {
    for(int T=rd();T;T--) solve();
}