BZOJ 4833 反演

已知 $ f(n)=2f(n-1)+f(n-2), f(0)=0,f(1)=1,g(n):=\text{lcm}\{f(1),f(2),\cdots,f(n)\} $ ,求

$$ \sum_{i=1}^nig(i) \mod p $$

Sol.

大致思路同 51nod 1223.

注意到 $ \gcd(f(n),f(m))=f(\gcd(n,m)) $ ,带入熟知结论得 $ g(n)=\prod_{T\sub[n]} f(\gcd_{i\in T}(i))^{(-1)^{|T|+1}} $ .

令 $ f(n)=\prod_{d|n} h(d) $ ,带入得

$$ \begin{align} g(n) &= \prod_{T\sub[n]}\left(\prod_{d|\gcd_{i\in T}(i)} h(d) \right)^{(-1)^{|T|+1}} \\ &= \prod_{d=1}^n h(d)^{\sum_{T\sub [\lfloor n/d \rfloor]}(-1)^{|T|+1}} \\ &= \prod_{d=1}^n h(d) \end{align} $$

求出 $ h $ 后问题是平凡的.

Code

#include <bits/stdc++.h>
using namespace std;
template<class T> void read(T& x)
{
    char c = getchar(); T p = 1, n = 0;
    while(c < '0' || c > '9') {if(c == '-') p = -1; c = getchar();}
    while(c >= '0' && c <= '9'){n = n * 10 + c - '0'; c = getchar();}
    x = p * n;
}
template<class T,class U>void read(T&x,U&y){read(x),read(y);}
template<class T,class U,class V>void read(T&x,U&y,V&z){read(x),read(y),read(z);}
const long long maxn = 5e6;
long long f[maxn], g[maxn];
inline long long power(long long a,long long b,long long p){long long ret=1;for(;b;b>>=1,a=1ll*a*a%p)if(b&1)ret=1ll*ret*a%p;return ret;}
int main()
{
    long long t; read(t);
    f[0] = 0, f[1] = 1;
    while(t--)
    {
        long long n; long long p; read(n, p);
        for(int i = 2; i <= n; ++i) f[i] = (2 * f[i - 1] + f[i - 2]) % p;
        for(int i = 1; i <= n; ++i) g[i] = f[i];
        for(int i = 1; i <= n; ++i)
        {
            long long inv = power(g[i], p - 2, p);
            for(int j = i + i; j <= n; j += i) g[j] = 1ll * g[j] * inv % p;
        }
        long long lcm = 1, ans = 0;
        for(int i = 1; i <= n; ++i) lcm = 1ll * lcm * g[i] % p, (ans += 1ll * lcm * i % p) %= p;
        printf("%d\n", ans);
    }
    return 0;
}

标签: none

添加新评论