题目大意: 求 \[a^b\ mod \ m\]
题解:
代码如下
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- ll a,m,phi;
- ll read(){
- ll x=0,f=0;char ch;
- do{ch=getchar();}while(!isdigit(ch));
- do{
- x=x*10+ch-'0';ch=getchar();
- if(x>=phi)f=1;
- x%=phi;
- }while(isdigit(ch));
- return f?x+phi:x;
- }
- ll calc(ll n){
- int ans=n;
- for(int i=2;i<=sqrt(n);i++)
- if(n%i==0){
- ans=ans/i*(i-1);
- while(n%i==0)n/=i;
- }
- if(n>1)ans=ans/n*(n-1);
- return ans;
- }
- ll fpow(ll n,ll b,ll c){
- ll res=1%c;
- for(;b;b>>=1,n=n*n%c)if(b&1)res=res*n%c;
- return res;
- }
- int main(){
- scanf("%d%d",&a,&m);
- phi=calc(m);
- ll b=read();
- printf("%lld\n",fpow(a,b,m));
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2995698.html