# 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 B. super_log 欧拉降幂

```#include <bits/stdc++.h>
#include <iostream>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <utility>
#include <cstdlib>
#include <cassert>
#include <ctime>
//#include <unordered_map>
#include <bitset>
#include <stack>
#include <sstream>
#include <algorithm>
#include <functional>
#include <numeric>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <list>
#include <set>
#include <iomanip>
#include <cctype>
#define sf scanf
#define gr getchar()
#define pf printf
#define sz(type) (type).size()
#define pb push_back
#define mp make_pair
#define IT iterator
using namespace std;
typedef long long ll;
inline ll qpow(ll,ll,ll);
const int N = 1e6+5;
int prime[N],tot;
ll phi[N],maxn = 1e6;

void pre(int n){
tot = 0;
phi[1] = 1;
memset(phi,0,sizeof(phi));
for(int i=2;i<=n;i++){
if(!phi[i]){
prime[tot++]=i;
phi[i]=1ll*(i-1);
}
for(int j=0;j<tot&&i*prime[j]<=n;j++){
if(i%prime[j]!=0) phi[i*prime[j]]=phi[i]*phi[prime[j]];
else{
phi[i*prime[j]]=1ll*prime[j]*phi[i];
break;
}
}
}
}
inline ll euler(ll n){
if(n <= 1ll*maxn) return phi[n];
ll ans = n;
for(int i=0;i<tot&&prime[i]*prime[i]<=n;i++){
if(n%prime[i]==0){
ans -= ans/prime[i];
while(n%prime[i]==0) n/=prime[i];
}
}
if(n > 1) ans -= ans/n;
return ans;
}
inline ll check(ll x,ll n,ll mod){
ll ans = 1;
for(ll i=1;i<=n;i++){
ans*=x;
if(ans >= mod) return ans;
}
return ans;
}

inline ll solve(ll a,int n,ll p){
if(n==0) return 1;
if(p==1) return 1;
ll exp = solve(a,n-1,euler(p)),ans;
ans = check(a,exp,p);
if(ans >= p) ans = qpow(a,exp,p) + p;
return ans;
}
int main(){
int t,b;
ll a,p;
pre(maxn);
sf("%d",&t);
while(t--){
sf("%lld%d%lld",&a,&b,&p);
pf("%lld\n",solve(a,b,p)%p);
}
return 0;
}

inline ll qpow(ll x,ll n,ll mod) {
ll ans = 1,a = x;
while(n) {
if(n&1) {
ans = ans*a%mod;
}
a = a*a%mod;
n>>=1;
}
return ans;
}```

0 条评论

• ### 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 F 主席树 或 滑动窗口

查询区间 [ id-k,id+k] 小于 val 的个数 num ， 再在该区间查询第 num 大的数。

• ### 大神碉堡！99 行代码实现的神奇效果

或许你不知道，电影和动画中特效有时仅仅短短的一秒，却可能需要高性能计算机演算一周，花费惊人。

• ### KDD 2019大奖新鲜出炉！华人博士勇夺最佳论文，“中国队”横扫KDD CUP

第25届ACM SIGKDD（数据挖掘及知识发现）于2019年8月4日-9日在美国阿拉斯加安克雷奇市举办。

• ### ICML 2020 放榜：北理工硕士一作拿下杰出论文奖，清华大学占据国内论文量榜首

昨日，国际机器学习顶会ICML 2020于“线上”公布了本届大会的杰出论文奖，获此殊荣的一共有两篇：

• ### 华人夺魁，「魔球」理论获奖：KDD 2019所有奖项出炉

第 25 届 ACM SIGKDD 知识发现和数据挖掘会议（KDD）已于今年 8 月 4 日在美国阿拉斯加州安克雷奇开幕。今年的大会奖项分为研究方向和应用数据科...

• ### 遥感数据、气象数据、土地土壤数据、农业数据、行政区数据...GIS数据获取网站整理

本文对GIS行业相关的综合数据获取网站加以整理，包括但不限于遥感数据、气候数据、土地数据、土壤数据、农业数据、行政区数据、社会数据、经济数据等。数据较多，大...

• ### 「中国法研杯」相似案例匹配竞赛结果出炉，冠军方案关键技术解读

2019 年 10 月 19 日，第十八届中国计算语言学大会「中国法研杯」相似案例匹配评测研讨会在云南昆明完美落幕。会上，清华大学刘知远副教授、中国科学院软件研...

• ### iCDO一周数据要闻：谷歌称Android免费模式或终结；京东地图首亮相；百度图腾上线推“区块链+版权”；B 站提供电商变现服务

7月19日 普华永道：中国互联网迎来“T2B2C”时代 2025年带来整体市值近50万亿