题目名有毒
由于并没有系统地开始学习数论,所以数论题基本靠暴力。
然鹅本题的题解相当简单:
emmm....我当你没说
一个简单易懂的方法是这样的:
1. 欧拉定理的推论
若正整数a,n互质,则对于任意正整数b,有 a^b≡a^(b mod φ(n)) (mod n)
2.欧拉函数
我们用1~n中与n互质的数的个数称为n的欧拉函数。
欧拉函数我们用φ(n)表示。
特殊地,当n为质数时,φ(n)=n-1.
那么我们可以综合以上知识
先求出b^c mod (p-1) ,再用快速幂求出a^(b^c mod (p-1))%p.
code
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a,b,c,p;
ll ksm(ll x,ll y,ll moder)
{
ll ans=;
while(y)
{
if(y&) ans=ans*x%moder;
y>>=;
x=x*x%moder;
}
return ans;
}
int main()
{
scanf("%lld%lld%lld%lld",&a,&b,&c,&p);
ll tmp=ksm(b,c,p-);
printf("%lld",ksm(a,tmp,p));
return ;
}