CF 757 E Bash Plays with Functions —— 积性函数与质因数分解

题目：http://codeforces.com/contest/757/problem/E

首先，f(n)=2，其中 m 是 n 的质因数的种类数；

而且

因为这个函数和1卷积，所以是一个积性函数，就可以每个质因子单独考虑；

而 f(p) = 2，对于每个质因子都一样！

所以可以 DP 预处理

而f(n) = f(p) * f(p) * ... * f(p)f(n) = dp[r][e] * dp[r][e] * ... * dp[r][e]

学到了质因数分解的新姿势！先预处理所有数的最小质因子，然后分解时直接除最小质因子，则复杂度就是 logn！

总之，真是一道好题！

代码如下：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

int const xn=1e6+,mod=1e9+;

int q,r,n,dp[xn][],mnp[xn];

int rd()

{

  int ret=,f=; char ch=getchar();

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

  while(ch>=''&&ch<='')ret=(ret<<)+(ret<<)+ch-'',ch=getchar();

  return f?ret:-ret;

}

int upt(ll x){while(x>=mod)x-=mod; while(x<)x+=mod; return x;}

void init()

{

  int mx=1e6; mnp[]=;

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

    if(!mnp[i])for(int j=i;j<=mx;j+=i)mnp[j]=i;//

  dp[][]=;

  for(int i=;i<=;i++)dp[][i]=;

  for(int i=,s=;i<=mx;i++,s=)

    for(int j=;j<=;j++)s=upt(s+dp[i-][j]),dp[i][j]=s;

}

int div(int x)

{

  int ans=;

  while(x!=)

    {

      int i=mnp[x],cnt=;

      while(x%i==)cnt++,x/=i;

      ans=((ll)ans*dp[r][cnt])%mod;

    }

  return ans;

}

int main()

{

  q=rd(); init();

  while(q--)

    {

      r=rd(); n=rd();

      printf("%d\n",div(n));

    }

  return ;

}