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

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

f0[n]=2^m，其中m是n的质因子个数（种类数）。大概是一种质因数只能放在 d 或 n/d 两者之一。

然后应该发现因为 f0 是积性的，所以 fr 也是积性的！因为是卷积得来的。

这样就能把每个质因数分开。对于每种质因数考虑 fr 的转移，则 f [ r ][ p^k ] = sigma(i:0~k) ( f [ r-1 ][ p^i ] ) 。

应该发现 f0 里每种质因数的值只和其次数有关，从转移可得出 f [ k ] 里的各种质因数的值也只和其次数有关！所以 dp 状态里只要记录次数就行。

学习到了质因数分解的更好而同样简单的方法。就是预处理mindiv，然后每次除以自己的mindiv。

先写了自己的原始方法，T了；于是怒写了个pollar rho，结果T得更快，难道是写错了？

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int N=1e6,M=,mod=1e9+;

int q,r,n,dp[N+][M+],s[M+],ans,mindiv[N+],cnt,pri[N+];

bool vis[N+];

int rdn()

{

  int ret=;bool fx=;char ch=getchar();

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

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

  return fx?ret:-ret;

}

void upd(int &x){x-=(x>=mod?mod:);}

void init()

{

  mindiv[]=;//

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

    {

      if(!vis[i])pri[++cnt]=i,mindiv[i]=i;

      for(int j=;j<=cnt&&(ll)i*pri[j]<=N;j++)

    {

      int d=i*pri[j];

      vis[d]=; mindiv[d]=pri[j];

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

    }

    }

}

int pw(int x,int k,int md)

{

  int ret=;while(k){if(k&)ret=(ll)ret*x%md;x=(ll)x*x%md;k>>=;}return ret;

}

bool MR(int x)

{

  if(x==)return true;

  int s=,u=x-,t=;

  while((u&)==)u>>=,t++;

  while(s--)

    {

      int a=rand()%(x-)+;//2~x-1

      a=pw(a,u,x);

      for(int i=,d;i<=t;i++)

    {

      d=(ll)a*a%x;

      if(d==&&a!=&&a!=x-)return false;

      a=d;

    }

      if(a!=)return false;

    }

  return true;

}

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

int Pl_rho(int x,int c)

{

  int x0=rand()%x,y=x,t=,k=;

  while()

    {

      x0=((ll)x0*x0+c)%(x+);

      int g=gcd(abs(x0-y),x);

      if(g!=&&g!=x)return g;

      if(x0==y)return x;

      if(++k==t)t<<=,y=x0;

    }

}

void fd_fc(int x)

{

  if(x<)return;

  if(MR(x))

    {

      int ret=;

      while(n%x==)n/=x,ret++;

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

      return;

    }

  int p=x;

  while(p==x)p=Pl_rho(p,rand()%(x-)+);//1~x-1

  fd_fc(p); fd_fc(x/p);

}

int main()

{

  dp[][]=;s[]=; init();

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

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

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

      dp[i][j]=s[j],s[j]=s[j-]+dp[i][j],upd(s[j]);

  q=rdn();

  while(q--)

    {

      r=rdn(); n=rdn(); ans=;

      //fd_fc(n);

      while(n!=)

    {

      int i=mindiv[n],d=;

      while(n%i==)n/=i,d++;

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

    }

      /*

      for(int i=mindiv[n],d;(ll)i*i<=n;i++)

    if(n%i==0)

      {

        d=0;

        while(n%i==0)d++,n/=i;

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

      }

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

      */

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

    }

  return ;

}