P4714 「数学」约数个数和

题意（假）：每个数向自己的约数连边，给出\(n,k(\le 10^{18})\)，询问\(n\)的约数形成的图中以\(n\)为起点长为\(k\)的链有多少条（注意每个点都有自环）

这样想是做不出来题的。

正常的题意是：询问\(n\)的约数的约数的....(共\(k\)次复读后)约数个数和。

考虑\(f_k(n)\)表示答案。

显然有\(f_{k}(n)=\sum_{d|n}f_{k-1}(d)\)

注意到用数论卷积的形式可以表示为

\[\mathtt f_k=\mathtt f_{k-1}*\mathtt {Id_0}
\]

因为\(\mathtt f_0=\mathtt d\)，即约数个数，又因为积性函数乘积性函数为积性函数

所以\(\mathtt f_k\)是积性函数。

考虑求\(\mathtt f_k(p^c)\)

我们有\(\mathtt f_k(p^c)=\sum_{i=0}^cf_{k-1}(p^i)\)

我们注意到每次\(k-1\),实际上是对\(p\)有一个划分，我们可以形象的理解为，\(c\)个物品，中间插\(k+1\)个板子，板子之间可以没有物品的方案数，其中物品无序，板子有序（因为每次只能从后往前放置）

根据插板法强制钦定板子的物品，可以得到

\[\mathtt f_k(p^c)=\binom{c+k+1}{k+1}
\]

这个\(c\)很小，直接算算就可以了。

分解大数可以直接使用Pollard_Rho算法

Code:

#include <cstdio>

#include <cctype>

#include <cstdlib>

#include <algorithm>

#define ll long long

using std::min;

const int SIZE=1<<21;

char ibuf[SIZE],*iS=ibuf,*iT=ibuf;

//#define gc() (iS==iT?(iT=(iS=ibuf)+fread(ibuf,1,SIZE,stdin),iS==iT?EOF:*iS++):*iT++)

#define gc() getchar()

template <class T>

void read(T &x)

{

    x=0;char c=gc();

    while(!isdigit(c)) c=gc();

    while(isdigit(c)) x=x*10+c-'0',c=gc();

}

const int pri[]={2,3,5,7,11,13,17,19,23,29,31,37};

void add(ll &a,ll b,ll p){a=a+b>=p?a+b-p:a+b;}

ll mul(ll d,ll k,ll p)

{

    ll f=0;

    while(k)

    {

        if(k&1) add(f,d,p);

        add(d,d,p);

        k>>=1;

    }

    return f;

}

ll qp(ll d,ll k,ll p)

{

    ll f=1;

    while(k)

    {

        if(k&1) f=mul(f,d,p);

        d=mul(d,d,p);

        k>>=1;

    }

    return f;

}

bool Miller_Rabin(ll n)

{

    if(n==1) return false;

    for(int i=0;i<12;i++) if(n%pri[i]==0) return n==pri[i];

    ll res=n-1;int k=0;

    while(!(res&1)) res>>=1,++k;

    for(int i=0;i<12;i++)

    {

        ll x=qp(pri[i],res,n);

        for(int j=0;j<k&&x>1;j++)

        {

            ll y=mul(x,x,n);

            if(y==1&&x!=n-1) return false;

            x=y;

        }

        if(x!=1) return false;

    }

    return true;

}

ll F(ll x,ll c,ll p) {return (mul(x,x,p)+c)%p;}

ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}

ll Find(ll n)

{

    ll x,y=rand()%n,c=rand()%n;

    int w=1<<9;

    for(int l=1;;l<<=1)

    {

        x=y;

        for(int i=0;i<l;i++) y=F(y,c,n);

        for(int i=0;i<l;i++)

        {

            int le=min(l-i,w);

            ll g=1,las=y;

            for(int j=0;j<le;j++) y=F(y,c,n),g=mul(g,(y+n-x)%n,n);

            g=gcd(g,n);

            if(g==1) continue;

            if(g==n)

            {

                g=1,y=las;

                while(g==1) y=F(y,c,n),g=gcd((y+n-x)%n,n);

            }

            return g;

        }

    }

}

ll s[1<<19],n,k,ans=1;

int tot;

void Pollard_Rho(ll n)

{

    if(n==1) return;

    if(Miller_Rabin(n)) {s[++tot]=n;return;}

    ll d=Find(n);

    while(d==n) d=Find(n);

    Pollard_Rho(d),Pollard_Rho(n/d);

}

const ll mod=998244353;

ll C(ll m,ll n)

{

    ll f=1;

    for(ll i=1;i<=n;i++) f=mul(f,i,mod);

    f=qp(f,mod-2,mod);

    for(ll i=m;i>m-n;i--) f=mul(f,i,mod);

    return f;

}

int main()

{

    read(n),read(k);

    Pollard_Rho(n);

    std::sort(s+1,s+1+tot);

    tot=std::unique(s+1,s+1+tot)-s-1;

    for(int i=1;i<=tot;i++)

    {

        ll c=0;

        while(n%s[i]==0) n/=s[i],++c;

        ans=mul(ans,C(c+k+1,c),mod);

    }

    printf("%lld\n",ans);

    return 0;

}

2019.4.29

巴特西

洛谷 P4714 「数学」约数个数和解题报告

P4714 「数学」约数个数和

最新文章

热门文章

巴特西

洛谷 P4714 「数学」约数个数和 解题报告

P4714 「数学」约数个数和

最新文章

热门文章

洛谷 P4714 「数学」约数个数和解题报告