【计蒜客14899】积性函数（加强版） 题解

题目出自北方大学acm多校训练赛第四场

V1（原题）

题目大意

  定义函数 $f(n,0)=1$， $f(n,m)=\sum_{d|n}f(d,m-1) \cdot f(\frac{n}{d},m-1)$
  给定 $n,m$，求 $f(n,m) \bmod 10007$
  多组数据，$T \le 10,\ n \le 10^9,\ m \le 50$

  （这题我想了十几分钟没想出来，然后jasonvictoryan走过来，想了10秒钟，想出了V2解法。。。）

题解

  据说 $n$ 的约数很少，直接暴力就。。。过了？？？

V2

题目大意

  数据范围改成 $T \le 10^3,\ n \le 10^{18},\ m \le 10^5$
  （这个模数感觉好容易误判。。。改成 $10^9+7$ 吧。。。）

题解

  长成 $f(i)=\sum_{d|n} f(d)*f(\frac{i}{d})$ 这个样子的，多半是积性函数。
  进而发现，同一层的 $f$ 是积性函数。（同一层是指 $m$ 相同）

  所以只用求出 $f(p_i^{c_i},m)$ 就行了，其中 $n=\Pi p_i^{c_i}$

  进而发现，这个东西跟 $p_i$ 没有关系，只跟 $c_i$ 有关。
  这里可能存在什么公式可以直接求出来，不过由于 $c_i<64$，所以预处理也行。

  然后大整数分解质因数用 pollard_rho。

代码

// 方法是 V2 的，数据范围是 V1 的，没打 pollard_rho
#include<cmath>
#include<cstdio>
#define fo(i,a,b) for(int i=a;i<=b;i++)
using namespace std;

const int mo=10007;

int n,m,p0,p[100][2];

int T,f[100][100];
int main()
{
    fo(i,0,30) f[i][0]=1;
	fo(j,1,50)
		fo(i,0,30)
            fo(k,0,i) f[i][j]=(f[i][j]+f[k][j-1]*f[i-k][j-1])%mo;
    
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d %d",&n,&m);
        
        int sqrtn=sqrt(n);
        p0=0;
        fo(i,2,sqrtn) if (n%i==0)
        {
            p[++p0][0]=i;
            p[p0][1]=0;
            for(; n%i==0; n/=i) p[p0][1]++;
        }
        if (n>1) p[++p0][0]=n, p[p0][1]=1;
        
        int ans=1;
        fo(i,1,p0) ans=ans*f[p[i][1]][m]%mo;
        
        printf("%d\n",ans);
    }
}