A. A simple Problem(2019武大校赛现场赛)(吉比特杯第二届湖北省程序设计大赛) 解题报告 Apare_xzc

A. A simple Problem(2019武大校赛现场赛)(吉比特杯第二届湖北省程序设计大赛) 解题报告

xzc 2019/4/15

题意：

求下列式子，其中有K个b

((((a)^b)^b)^b...)^b  % p

数据范围：
  1<=a,b,p<=1E7
  1<=k<=1E18

输入：
  第一行一个T，代表T组数据
  下面有T行，每行4个数，a,b,k,p

输出：
T行，每行一个整数

样例输入：

3
2 3 1 10000
3 2 2 80
342 234 567 89

样例输出：

8
1
2

思路：

拓展欧拉定理：

a^b%p = a^(b%phi[p]+phi[p]) % p   ( b>phi[p] )

a^b%p = a^(b%phi[p]) % p   ( b<=phi[p] )

• Phi[p]的衰减速度很快，不到100次就会变为1，然后任意数%1=0
• 所以我们递归求解即可
• 判断k个b的幂是否>p可以在求快速幂时，顺便处理出来
• 具体见代码

我的代码：

/* Author: xzc time: 723ms status：AC A. A simple problem */
#include<bits/stdc++.h>
#define For(i,a,b) for(register int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(register int i=(a);i>=(b);--i)
#define Mst(a,b) memset(a,(b),sizeof(a))
#define LL long long
using namespace std;
const int maxn  =1e7+100;
int sushu[maxn/10];
bool notPrime[maxn];
int phi[maxn];
void getPhiTable(int * p); 
LL fast_pow(bool & ok,LL a,LL b,LL m)  
{   //快速幂，oK用于返回a^b是否大于m 
	ok = false;
	LL ans = 1;
	while(b)
	{
		if(b&1)
		{
			ans = ans*a;
			if(ans>m) ok = true;
			if(ans>=m) ans %= m;	
		} 
		a = a*a;
		if(a>m) ok = true;
		if(a>=m) a%=m;
		b>>=1; 
	}
	return ans;
}
LL f(bool & big,LL b,LL k,LL p,bool &flag) //求 (((b^b)^b)...) % p
{   //flag用于记录之前小于K个b的幂是否大于p 
	//printf("进入了第%lld层，要计算%lld个%lld %% %lld\n",k,k,b,p); 
	if(k==1)
	{
		if(b>p) b = b%p+p,flag = true;
		else b = b%p;
		return b;
	}
	if(p==1) return 1;
	bool ok = false;
	LL y = f(ok,b,k-1,phi[p],flag);
	if(ok||flag) y += phi[p],flag = true; 
	//printf("回到了第%lld层，要计算pow(%lld,%lld,%lld)\n",k,b,y,p); 
	return fast_pow(big,b,y,p); 
}
/* 4 87 2 77 83 29 2 53 57 9122259 6 57 57 50 4 35 9684961 Answer: 70 4 39 9211933 */
int main()
{
	//freopen("02.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	getPhiTable(phi);
	int T;
	LL a,b,p,k;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld%lld%lld",&a,&b,&k,&p);
		int pp = phi[p];	
		bool ok = false;
		bool flag = false;
		LL zz = f(ok,b,k,pp,flag);///zzz = (((b^b)^b)...) % pp K个b 
		if(ok||flag) zz += pp;
		LL ans = fast_pow(ok,a,zz,p);
		printf("%lld\n",ans);
	}	
	return 0;
} 
void getPhiTable(int *p)
{
	int cnt = 0;
	int n = maxn-50;
	p[1] = 1;
	For(i,2,n)
	{
		if(!notPrime[i])
		{
			sushu[cnt++] = i;
			p[i] = i-1;		
		}
		for(int j=0;j<cnt&&1ll*i*sushu[j]<=n;++j)
		{
			notPrime[i*sushu[j]] = true;
			if(i%sushu[j])
				p[i*sushu[j]] = p[i]*(sushu[j]-1);
			else
			{
				p[i*sushu[j]] = p[i]*(sushu[j]);
				break;
			}
		}
	}	
}