高速べき乗!!!

722 ワード

???高速べき乗は何ですか??
正確な定義は詳細に検索できます
ここで栗を挙げて快速べき乗とは何かを説明します
3文字のA B Cを与える
AのB次方がCを型取りした結果、高速べき乗が求めた結果です!
ある同級生はこれが簡単ではないかと言った.公式を直接並べばいいのではないでしょうか.so easy!
ButここでのA B Cは、1<=A,B,C<=10^9の範囲である.
これで直接公式を使って直接演算してしまうと、それはダメなので、システムが崩れてしまいます!!
だからl高速べき乗を使います.
コード:
 
#include
#include
#include
using namespace std;


typedef long long ll;
ll kuai(ll a,ll b,ll c)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%c;
		a=a*a%c;
		b>>=1;
	}
	return res;
}


int main()
{
	
	int a,b,c;
	scanf("%d%d%d",&a,&b,&c);
	printf("%d
",kuai(a,b,c)); return 0; }