快速幂典型

题目描述

求 a 乘 b 对 p 取模的值，其中 1≤a,b,p≤1018。

输入描述:

第一行a，第二行b，第三行p。

输出描述:

一个整数，表示a×bmodp的值。

示例1

输入

2
3
9

输出

6

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod=1e9+7;
const int M=4e4+10;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int minn=0x3f3f3f3f;
int maxn=0xc0c0c0c0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
ll n,m,s,e,k,h,a,b,l,r,x,p;
ll qpow(ll a,ll b,ll p)
{ll ans=0;while(b){if(b&1)ans=(ans+a)%p;a=a*2%p;b>>=1;}return ans;
}
void solve()
{cin>>a>>b>>p;cout<<qpow(a,b,p)<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t=1;
//	cin>>t;while(t--){	solve();}return 0;
}

题目描述

求 a 的 b 次方对 p 取模的值，其中0≤a,b,p≤109​，p>0

输入描述:

三个用空格隔开的整数a,b和p。

输出描述:

一个整数，表示abmodp的值。

示例1

输入

2 3 9

输出

8

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int mod=1e9+7;
const int M=4e4+10;
const int N=1e5+10;
const int INF=0x3f3f3f3f;
int minn=0x3f3f3f3f;
int maxn=0xc0c0c0c0;
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
ll n,m,s,e,k,h,a,b,l,r,x,p;
ll qpow(ll a,ll b,ll p)
{ll ans=(ll)1%p;while(b){if(b&1)ans=ans*a%p;a=a*a%p;b>>=1;}return ans;
}
void solve()
{cin>>a>>b>>p;cout<<qpow(a,b,p)<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t=1;
//	cin>>t;while(t--){	solve();}return 0;
}