题目大意

已知函数：
给定一些正整数对(ni, ci)，输出fci(ni)对1e9+7取余的值。

解题思路

官方题解已经简洁地叙述了：

观察公式，fc (x) 其实是 c 的若干次方，且指数要尽量大。最好的情况下，每次只消掉一个质因子。所以 fci(ni)就是cx的质因子个数。

我想到的是使用递归从n开始，每个数除了自己外最大的因数，直到一个素数或1。记录这个过程中递归层数，即要求c的几次幂。上来就打表存储，提升效率。（实际上和题解没区别）

AC代码 

#include<bits/stdc++.h>
using namespace std;
int a[1000010],t,n,c;
const long long mod=1e9+7;
void hh(int x)
{
    if(a[x]) return;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
        {
            hh(x/i);
            a[x]=a[x/i]+1;
            return;
        }
    a[x]=1;
    return;
}
long long ks(long long x,int y)
{
    long long ans=1;
    while(y)
    {
        if(y&1) ans=ans*x%mod;
        y>>=1,x=x*x%mod;
    }
    return ans;
}
int main()
{
    a[1]=0;
    for(int i=2;i<=1000000;i++) hh(i);
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&c);
        //hh(n);
        printf("%lld\n",ks((long long)c,a[n]));
    }
    return 0;
}