专栏首页wym南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 B. super_log 欧拉降幂

南京网络预选赛 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 H. Holy Grail 多源最短路

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

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

    用户2965768
  • 大神碉堡!99 行代码实现的神奇效果

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

    逆锋起笔
  • KDD 2019大奖新鲜出炉!华人博士勇夺最佳论文,“中国队”横扫KDD CUP

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

    新智元
  • ICML 2020 放榜:北理工硕士一作拿下杰出论文奖,清华大学占据国内论文量榜首

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

    AI科技评论
  • 华人夺魁,「魔球」理论获奖:KDD 2019所有奖项出炉

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

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

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

    郭好奇同学
  • 「中国法研杯」相似案例匹配竞赛结果出炉,冠军方案关键技术解读

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

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

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

    iCDO互联网数据官

扫码关注云+社区

领取腾讯云代金券