当前位置: 首页 > biancheng >正文

牛客练习赛#84 F 莫比乌斯反演+杜教筛+技巧+斐波那契数列和gcd的结论+矩阵快速幂

题意:

给出 n , k n,k n,k,计算
∑ i 1 = 1 n ∑ i 2 = 1 n . . . ∑ i n = 1 n g c d ( f i 1 , f i 2 , . . . , f i n ) \sum_{i_{1}=1}^{n}\sum_{i_{2}=1}^{n}...\sum_{i_{n}=1}^{n}gcd(f_{i_{1}},f_{i_{2}},...,f_{i_{n}}) i1=1ni2=1n...in=1ngcd(fi1,fi2,...,fin)

Solution:

这题结论有点多,先给出来,后附第二条的证明,第一条难度太大

结论 1 1 1

g c d ( f i 1 , f i 2 , . . . . , f i n ) = f g c d ( i 1 , i 2 , . . . , i n ) gcd(f_{i_{1}},f_{i_{2}},....,f_{i_{n}})=f_{gcd(i_{1},i_{2},...,i_{n})} gcd(fi1,fi2,....,fin)=fgcd(i1,i2,...,in)

于是即计算
∑ i 1 = 1 n ∑ i 2 = 1 n . . . ∑ i n = 1 n f g c d ( i 1 , i 2 , . . . , i n ) \sum_{i_{1}=1}^{n}\sum_{i_{2}=1}^{n}...\sum_{i_{n}=1}^{n}f_{gcd(i_{1},i_{2},...,i_{n})} i1=1ni2=1n...in=1nfgcd(i1,i2,...,in)
显然枚举因子,这里因子为 g c d gcd gcd项,即
∑ d = 1 n f d ∑ i 1 = 1 n ∑ i 2 = 1 n . . . ∑ i n = 1 n [ g c d ( i 1 , i 2 , . . . , i n ) = d ] \sum_{d=1}^{n}f_{d}\sum_{i_{1}=1}^{n}\sum_{i_{2}=1}^{n}...\sum_{i_{n}=1}^{n}[gcd(i_{1},i_{2},...,i_{n})=d] d=1nfdi1=1ni2=1n...in=1n[gcd(i1,i2,...,in)=d]
这是个莫比乌斯反演的经典形式了
∑ d = 1 n f d ∑ i 1 = 1 ⌊ n d ⌋ ∑ i 2 = 1 ⌊ n d ⌋ . . . ∑ i n = 1 ⌊ n d ⌋ [ g c d ( i 1 , i 2 , . . . , i n ) = 1 ] = ∑ d = 1 n f d ∑ i 1 = 1 ⌊ n d ⌋ ∑ i 2 = 1 ⌊ n d ⌋ . . . ∑ i n = 1 ⌊ n d ⌋ ∑ t ∣ g c d ( i 1 , i 2 , . . . , i n ) μ ( t ) \sum_{d=1}^{n}f_{d}\sum_{i_{1}=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{i_{2}=1}^{\lfloor \frac{n}{d} \rfloor}...\sum_{i_{n}=1}^{\lfloor \frac{n}{d} \rfloor}[gcd(i_{1},i_{2},...,i_{n})=1]=\sum_{d=1}^{n}f_{d}\sum_{i_{1}=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{i_{2}=1}^{\lfloor \frac{n}{d} \rfloor}...\sum_{i_{n}=1}^{\lfloor \frac{n}{d} \rfloor}\sum_{t|gcd(i_{1},i_{2},...,i_{n})}\mu(t) d=1nfdi1=1dni2=1dn...in=1dn[gcd(i1,i2,...,in)=1]=d=1nfdi1=1dni2=1dn...in=1dntgcd(i1,i2,...,in)μ(t)
再次优先枚举因子,这里为 t t t
∑ d = 1 n f d ∑ t = 1 ⌊ n d ⌋ μ ( t ) ⌊ n d t ⌋ k \sum_{d=1}^{n}f_{d}\sum_{t=1}^{\lfloor \frac{n}{d} \rfloor}\mu(t)\lfloor \frac{n}{dt} \rfloor^{k} d=1nfdt=1dnμ(t)dtnk

到这里,我的思路为枚举 T = d t T=dt T=dt,即计算
∑ T = 1 n ⌊ n T ⌋ k ∑ d ∣ T μ ( d ) f ( T d ) \sum_{T=1}^{n}\lfloor \frac{n}{T} \rfloor^{k}\sum_{d|T}\mu(d)f(\frac{T}{d}) T=1nTnkdTμ(d)f(dT)
第二个求和形式极其像莫比乌斯反演的变换形式,但很可惜,斐波那契数列不是一个积性函数,否则将是绝杀,只能作罢

不能化简的话,有一个技巧,第二个求和发现上界是一个下取整,把他令成一个函数
R ( x ) = ∑ i = 1 x μ ( i ) ⌊ x i ⌋ R(x)=\sum_{i=1}^{x}\mu(i)\lfloor \frac{x}{i} \rfloor R(x)=i=1xμ(i)ix
先把他代入原式我们再分析他的妙处,原式即
∑ d = 1 n f d R ( ⌊ n d ⌋ ) \sum_{d=1}^{n}f_{d}R(\lfloor \frac{n}{d} \rfloor) d=1nfdR(dn)
首先,这个表达式有下取整,可以数论分块;其次, R ( x ) R(x) R(x)内部也有下取整,又可以数论分块,并且求 R ( x ) R(x) R(x)需要 μ \mu μ的前缀和,这恰好就是杜教筛!

解决了 R ( x ) R(x) R(x)部分,那么求上式也需要 f f f的前缀和,如何处理?

结论 2 2 2

∑ i = 1 n f i = f n + 2 − 1 \sum_{i=1}^{n}f_{i}=f_{n+2}-1 i=1nfi=fn+21

那么只需要求斐波那契的一个项即可,矩阵快速幂即可轻松做到

结论 2 2 2证明:

利用累加法,设 S ( n ) S(n) S(n)为斐波那契数列的前 n n n项和:
f 3 = f 2 + f 1 f 4 = f 3 + f 2 . . . f n = f n − 1 + f n − 2 f_{3}=f_{2}+f_{1}\\ f_{4}=f_{3}+f_{2}\\ ...\\ f_{n}=f_{n-1}+f_{n-2}\\ f3=f2+f1f4=f3+f2...fn=fn1+fn2
对应位置全部相加,得到:
S ( n ) − f 1 − f 2 = ( S ( n ) − f 1 − f n ) + ( S ( n ) − f n − 1 − f n ) S(n)-f_{1}-f_{2}=(S(n)-f_{1}-f_{n})+(S(n)-f_{n-1}-f_{n}) S(n)f1f2=(S(n)f1fn)+(S(n)fn1fn)
f 1 = f 2 = 1 f_{1}=f_{2}=1 f1=f2=1,合并得到
S ( n ) = 2 f n + f n − 1 − 1 S(n)=2f_{n}+f_{n-1}-1 S(n)=2fn+fn11
递推公式合并右式,就得到了
S ( n ) = f n + 2 − 1 S(n)=f_{n+2}-1 S(n)=fn+21
同理是可以得到奇数项和,偶数项和的

// #include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#include<bitset>
#include<map>
using namespace std;

using ll=long long;
const int N=2e5+5,inf=0x3fffffff;
const long long INF=0x3fffffffffffffff,mod=1e9+9;

ll qm(ll x){return (x%mod+mod)%mod;}

struct matrix
{
    ll a[2][2];
    void initial(){memset(a,0,sizeof(a));}
    void build()
    {
        initial();
        for(int i=0;i<2;i++) a[i][i]=1;
    }
    ll* operator[](int i) const {
        return (ll*)&a[i][0];
    }
    matrix operator*(const matrix& x) const
    {
        matrix ret; ret.initial();
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                for(int k=0;k<2;k++) ret[i][j]=(ret[i][j]+a[i][k]*x[k][j]%mod)%mod;
        return ret;
    }
}ans={{
    {1,1},
    {0,0}
}},tmp={{
    {1,1},
    {1,0}
}};

matrix qpow(matrix a,ll b)
{
    matrix ret,base=a; ret.build();
    while(b)
    {
        if(b&1) ret=ret*base;
        base=base*base;
        b>>=1;
    }
    return ret;
}

ll f(int x)
{
    if(x<=2)
    {
        if(x==0) return 0;
        return 1;
    }
    return qm((ans*qpow(tmp,x-2))[0][0]);
}

ll fpre(int x){return qm(f(x+2)-1);}

ll qpow(ll a,ll b)
{
    ll ret=1,base=a;
    while(b)
    {
        if(b&1) ret=ret*base%mod;
        base=base*base%mod;
        b>>=1;
    }
    return ret;
}

int mu[N],cnt,prime[N];
bool nt[N];
map<int,ll>map1;

void make_prime()
{
    mu[1]=1;
    for(int i=2;i<N;i++)
    {
        if(!nt[i]) prime[++cnt]=i,mu[i]=mod-1;
        for(int j=1;j<=cnt&&i*prime[j]<N;j++)
        {
            nt[i*prime[j]]=true;
            if(i%prime[j]==0) break;
            else mu[i*prime[j]]=qm(1ll*mu[i]*mu[prime[j]]);
        }
    }
    for(int i=1;i<N;i++) mu[i]=qm(1ll*mu[i]+1ll*mu[i-1]);
}

ll calcmu(int x)
{
    if(x<N) return 1ll*mu[x];
    if(map1.count(x)) return map1[x];
    ll ret=1;
    for(int l=2,r;l<=x;l=r+1)
    {   
        r=x/(x/l);
        ret=qm(ret-(r-l+1)*calcmu(x/l));
    }
    return map1[x]=ret;
}

int n,k;

ll R(int x)
{
    ll ret=0;
    for(int l=1,r;l<=x;l=r+1)
    {
        r=x/(x/l);
        ret=qm(ret+qm(calcmu(r)-calcmu(l-1))*qpow(x/l,k));
    }
    return ret;
}

int main()
{
    make_prime();
    cin>>n>>k; ll res=0;
    for(int l=1,r;l<=n;l=r+1)
    {
        r=n/(n/l);
        res=qm(res+qm(fpre(r)-fpre(l-1))*R(n/l));
    }
    cout<<res;
    return 0;  
}

相关文章:

  • 牛客练习赛#84 F 莫比乌斯反演+杜教筛+技巧+斐波那契数列和gcd的结论+矩阵快速幂
  • ZZNUOJ_用C语言编写程序实现1342:支配值数目(附完整源码)
  • java毕业设计后勤管理系统餐饮评价监督系统(附源码、数据库)
  • 前端基础学习笔记
  • 【TS】联合类型--类型断言--类型推断
  • 谈笑风声的秘密
  • QT影城网上售票系统
  • NetCDF数据在ArcMap中的使用
  • 打怪升级(考验思路)
  • 持续精进,改变自己