题解 | #小红玩幂塔#

小红玩幂塔

https://ac.nowcoder.com/acm/contest/26086/D

ana↑↑n的因子数量,看到幂塔首先想到的是欧拉降幂。又有若aa分解质因数为 pix\prod p_i ^ x ,那么aa的因子数量为 (xi+1)\prod(x_i+1),所以我们可以将ana↑↑n表示为pic\prod p_i ^ c ,其中cic_ixia(n1)x_i*a↑↑(n-1) 。只需要预处理出来 a(n1)a↑↑(n-1),计算每个cic_i,最后的结果为(ci+1)\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';
}
全部评论
为什么在那里需要重写取模
1
送花
回复 分享
发布于 2022-01-01 18:25

相关推荐

07-16 16:00
已编辑
辽宁大学 运营
#非技术投递记录#&nbsp;末2❶百度特意挑了个招的人多的岗,嘿嘿万一就让我进去了呢7.10投递❷中新赛克这名字没听过,但是在南京,我小时候去南京玩,可热可热了。但是盐水鸭特别好吃。还有万三蹄。7.10投递❸京东原本以为京东进军kpl能收购我喜欢的战队的,结果买了vg,伤心。7.10投递7.11测评,性格也不知道他们想要啥样的人,我都是按当牛做马没长脑子的老实人选的。当年语文非连续性文本学的可好了,现在测评一个比一个答得差,嘿嘿。还考我逻辑,我要是有那东西我不就考研去了,我都要笨死了❺传音控股就一个文科岗,说是一年给三十多万,天呐这不投更待何时。7.11投递❻点点互动游戏企业,说真的我虽然爱玩游戏但是很菜,深谙vc才能赢,如果要是推进我再了解了解。7.11投递❼莉莉丝也是游戏企业,投了个战略,一个发行。一想到我投了战略研究员我就想笑,哈哈哈我怎么还战略研究员了7.11投递❽联基集团群里看到的,没听过啊,小红书连避雷都没有,但是又叫集团,我一看连一个招聘网站都没有,还得投邮箱。找营销,虽然我是金融但我还是投了,天杀的金融除了给当柜员老头老太太发养老金没有别的出路了吗。7.13投递❾腾讯产品经理管培生,这工作好啊,一出来就是经理。计算机理工科背景加分,鹅你录我我回头就拿出三天python&nbsp;87的精神学你。虽然大概率是分母,但是投就完了。7.13投递❿当当网也是一个投邮箱的,招运营采购啥的,采购也挺好,听说md采购20薪不知道真假7.15投递❿❶卓驭不招运营但是招产品经理,我这东一榔头西一棒槌的工作经验里巴拉巴拉还真有产品相关,我要是有可能进大疆,第一件事就是买一个pocket&nbsp;3,&nbsp;馋好久了7.15投递7.16测评❿❷科大讯飞产品运营居然有音乐方向,完完全全垂直经历哈哈哈哈哈哈我来了,能投俩,那我再投个产品运营7.15投递7.16测评 #本周投递记录#
点赞 评论 收藏
分享
7 收藏 评论
分享
牛客网
牛客企业服务