A simple Blog for wyx I've been down the bottle hoping.
1355 斐波那契的最小公倍数 数论变换 莫比乌斯反演
发表于: | 分类: Oi | 评论:0 | 阅读:234

给定$n$个数字,求他们对应的斐波那契数列项的最小公倍数,$n \le 5\times 10^5,a_i \le 10^6$

做完这题发现bz月赛就是在搞笑

注意到斐波那契数列有这样一个性质,$\gcd(f(i),f(j))=f(\gcd(i,j))$

然后这题就能做了

考虑$lcm(S)=\prod_{T\subseteq S}\gcd(f(T))^{(-1)^{|T|+1}}$

然后$lcm(S)=\prod_{T\subseteq S}f(\gcd(T))^{(-1)^{|T|+1}}$

老套路,考虑构造一个数列$g$,满足$f(n)=\prod_{d|n}g(d)$,把它带进去

$lcm(S) = \prod_{T\subseteq S}\prod_{d|gcd(T)}g(d)^{(-1)^{|T|+1}}$

然后我们枚举$g(d)$的贡献,

$lcm(S) = \prod_{d=1}g(d)^{\sum_{T\subseteq S, d|T}(-1)^{|T|+1}}$

考虑他的指数$\sum_{T\subseteq S, d|T}(-1)^{|T|+1}$

$$\sum_{T\subseteq S,T\neq \emptyset,d| { T }}(-1)^{|T|+1}=\begin{cases}
1, & \exists a\in S,d|a \newline
0, & \text{otherwise}
\end{cases} $$

为啥?

我们假设有$p$个数字满足d是他的一个约数,那么考虑那个数字应该就是

$\sum_{i=1}^p(-1)^(i+1)C_p^i$, 考虑在前面补上一项$(-1)C_p^0$

然后整个式子提出一个负号出来就变成了一个$\sum_{i=0}^p (-1)^i C_p^i$

然后这个东西显然就变成了$(-1+1)^p$,加上刚才补得1答案就是1了非常完美

第二个的话显然是0了……毕竟都是空集

然后我们就get了

$$lcm(f(S)) = \prod_{\exists a \in S, d|a} g_d$$

注意到$g(x)=\prod_{d|x}f(d)^{\mu(\frac{x}{d})}$,所以$n\log(n)$就做完了

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int mod = 1000000007;
const int N = 1000000+5;

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int f[N], g[N], h[N], T[N];

inline int pow(int a,int b) {
    LL res = 1;
    for(;b;b>>=1,a=(LL)a*a%mod)
        if(b&1)
            res = (LL) res * a % mod;
    return res;
}

int prime[N], cnt, mu[N], inv[N];
bool F[N];

inline void init() {
    mu[1] = 1;
    int Max = N - 4;
    for(int i = 2; i <= Max; ++i) {
        if(!F[i]) {
            mu[i] = -1;
            prime[++cnt] = i;
        }
        for(int j=1;prime[j]*i<=Max;++j) {
            F[i*prime[j]] = 1;
            if(i%prime[j]==0) break;
            mu[i*prime[j]] = -mu[i];
        }
    }
}

int main() {
    init();
    int n = read();
    register int i;
    for(i=1;i<=n;++i) {
        int temp = read();
        h[i] = temp;
        T[temp] = 1;
    }
    int d, j;
    f[1] = 1, f[2] = 1;
    for(i=3;i<=N-4;++i) f[i] = (f[i-1] + f[i-2]) % mod;
    for(i=1;i<=N-4;++i) g[i] = 1;
    for(i=1;i<=N-4;++i) inv[i] = pow(f[i], mod-2);
    int Max = N - 4, x;
    for(d=1;d<=Max;++d) {
            for(i=1;i*d<=Max;++i) {
                x = i * d;
                if(mu[i] == 1) 
                    g[x] = (LL) g[x] * f[d] % mod;
                else if(mu[i] == -1) 
                    g[x] = (LL) g[x] * inv[d] % mod;
            }
        }
    LL ans = 1;
    for(i=1;i<Max;++i) 
        for(j=1;j*i<=Max;++j) 
            if(T[i*j]) {
                ans = ans * g[i] % mod;
                break;
            }
    cout << ans << endl;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP