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;}}}
}










