BZOJ 4833 反演

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

添加新评论

bst g22 jinniu lilai opebet orange88 vinbet xbet yuebo zunlong shijiebei bet007 hg0088 ju111 letiantang m88 mayaba qg777 qianyiguoji sbf777 tengbohui tlc ule weilianxier waiweitouzhu xingfayule xinhaotiandi yinheyule youfayule zhongying 2018shijiebei w88 18luck 188bet beplay manbet 12bet 95zz shenbo weide1946 ca88 88bifa aomenxinpujing betway bodog bt365 bwin tongbao vwin weinisiren 88jt fenghuangyule hongyunguoji 918botiantang huanyayule jianada28 jixiangfang libo long8 hongzuyishi zuqiutouzhu