取余运算||快速幂

题目描述

输入b，p，k的值，求b^p mod k的值。其中b，p，k*k为长整型数。

输入输出格式

输入格式：

三个整数b,p,k.

输出格式：

输出“b^p mod k=s”

s为运算结果

#include<iostream>
#include<cstdio>
using namespace std;
long long  a,b,s;
int res=1;
int pw(int j,int k)
{
	if(k==0)
	{
		res=res%s;
		return res;
	}
	j=j%s;
	if(k%2==1)
	{
		res=res*j;
		res=res%s;
		k--;
		pw(j,k);
	}
	else
	{
		k=k/2;
		j=j*j;
		pw(j,k);
	}	
}
int main()
{
	cin>>a>>b>>s;
	long long x=1;
	x=pw(a,b);
	cout<<a<<"^"<<b<<" mod "<<s<<"="<<x;
}