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

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

28

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
#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
",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)
",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 9684961Answer: 
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
",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;}}}	
}