[Codeforces 757E] Bash Plays with Functions (数论)

题目链接： http://codeforces.com/contest/757/problem/E?csrf_token=f6c272cce871728ac1c239c34006ae90

题目：

题解：

$f_0(n) = 2^{n的不同质因子的个数}$

$ f_r(n) = \sum_{d|n}f_{r-1}(d)$

$f_0$是积性函数 , $f_r = f_0 * Id^r (1) $也是积性函数 , 所以只需要求$f_r(p^k)$就行了

$f_r(p^k)$与p无关 , $f_0(p^k)$=1+(k!=0) , $f_r(p^k)$=$\sum_{0<=i<=k}$ $ f_{r-1}(p^i)$

先递推出所有 (r,k) 的函数值, 每个询问只要分解质因数即可

时间复杂度: O((r + q) logn)

代码如下：

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

#include<cmath>

using namespace std;

typedef long long ll;

const int N=1e6+;

const int M=;

const int mod=1e9+;

int q,r,n,tot;

int prime[N],vis[N];

ll f[N][];

inline int read()

{

    char ch=getchar();

    int s=,f=;

    while (ch<''||ch>'') {if (ch=='-') f=-;ch=getchar();}

    while (ch>=''&&ch<='') {s=(s<<)+(s<<)+ch-'';ch=getchar();}

    return s*f;

}

void get_prime()

{

    for (int i=;i<=N;i++)

    {

        if (!vis[i]) prime[++tot]=i;

        for (int j=;j<=tot&&prime[j]*i<=N;j++)

        {

            vis[prime[j]*i]=;

            if (i%prime[j]==) break;

        }

    }

}

void pre()

{

    f[][]=;

    for (int i=;i<=M;i++) f[][i]=;

    for (int i=;i<=N;i++)

    {

        ll sum=;

        for (int j=;j<=M;j++)

        {

            sum+=f[i-][j];

            f[i][j]=(f[i][j]+sum)%mod;

        }

    }

}

int main()

{

    get_prime();

    pre();

    q=read();

    while (q--)

    {

        r=read();n=read();

        ll ans=;

        for (int i=;i<=tot&&prime[i]<=sqrt(n);i++)

        {

            if (n%prime[i]) continue;

            int num=;

            while (n%prime[i]==) n/=prime[i],num++;

            ans=1ll*ans*f[r][num]%mod;

        }

        if (n>) ans=1ll*ans*f[r][]%mod;

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

    }

    return ;

}

巴特西

[Codeforces 757E] Bash Plays with Functions (数论)

题目链接： http://codeforces.com/contest/757/problem/E?csrf_token=f6c272cce871728ac1c239c34006ae90

题目：

题解：

最新文章

热门文章