题解 | #小红玩幂塔#

求$a\uparrow \uparrow na\uparrow \uparrow n$的因子数量，看到幂塔首先想到的是欧拉降幂。又有若$aa$分解质因数为 $\prod p_i^x\backslash prod\; p\_i\; ^\; x$ ,那么$aa$的因子数量为 $\prod (x_i+1)\backslash prod(x\_i+1)$，所以我们可以将$a\uparrow \uparrow na\uparrow \uparrow n$表示为$\prod p_i^c\backslash prod\; p\_i\; ^\; c$ ,其中$c_{i}c\_i$为$x_i\ast a\uparrow \uparrow (n-1)x\_i*a\uparrow \uparrow (n-1)$ 。只需要预处理出来 $a\uparrow \uparrow (n-1)a\uparrow \uparrow (n-1)$,计算每个$c_{i}c\_i$，最后的结果为$\prod (c_i+1)\backslash prod(c\_i+1)$。

代码如下

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<int,int> mp;
int p=1000007;
int phi(int x){
	if(mp.count(x)) return mp[x];
	int res=x;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
			res-=res/i;
			while(x%i==0) x/=i;
		}
	}
	if(x>1) res-=res/x;
	return mp[x]=res;
}
ll mod(ll a,ll b){  //重写取模
	if(a<b) return a;
	return a%b+b;
}
ll qs(ll a,ll b,ll p){
	ll res=1;
	while(b){
		if(b&1) res=mod(res*a,p);
		a=mod(a*a,p);
		b>>=1;
	}
	return res;
}
int a,n;
ll get(int a,int n,int p){
	if(n==1||p==1) return mod(a,p);
	return qs(a,get(a,n-1,phi(p)),p);
}
int main()
{
	cin>>a>>n;
	
	int res=1;
	int t;
	if(n==1) t=1;
	else t=get(a,n-1,p);
	for(int i=2;i*i<=a;i++){
		if(a%i==0){
			int cnt=0;
			while(a%i==0) a/=i,cnt++;
			res=1ll*res*(cnt*t%p+1)%p;
		}
	}
	if(a>1) res=1ll*res*(t%p+1)%p;
	cout<<res<<'\n';
}