ブルーブリッジカップJOEの算数C++アルゴリズムHERODINGのブルーブリッジカップを高める道

リソース制限時間制限:1.0 sメモリ制限:256.0 MB問題記述ある日、JOEはab%cの計算という平凡な演算に耐えられなくなった.だから彼はあなたにab%cを計算するプログラムを書くように要求した.
ヒント:bが奇数の場合、ab=(a(b/2))2*a、そうでない場合ab=(a(b/2))2.入力フォーマットの3つの非負の整数a,b,c;出力フォーマットはa^b%cを表す整数ansである.サンプル入力7 2 5サンプル出力4データ規模と約30%a<=100,b<=10^4,1<=c<=100 60%a<=10^4,b<=10^5,1<=c<=10^4 100%a<=10^6,b<=10^9,1<=c<=10^6
问题を解く考え方:第一眼看题干、改造^符号だと思って、よく観察してやっと発见して、この问题の本质はべき乗を求めて型を取って、しかもそれは私达に型を取った1つのかなり巧みな考えを提供して、毎回平方の后で、bの係数は半減して、以前の循环にbを乗じて副次的にずっと速くなって、毎回平方の后の结果を初期値として持ち込んで、このように绝えず循环して、サイクル数はルート番号の下のbで、効率は大いに向上して、もちろんbの奇数偶数の問題に注意して、コードは以下の通りです:

#include

using namespace std;

int main(){
	long long ans, a, b, c;
	cin >> a >> b >> c;
	ans = 1;
	a %= c;
	while(b)
	{
		if(b % 2 == 1){
			ans = (ans * a) % c;
		}
		b /= 2;
		a = (a * a) % c;
	}
	cout << ans << endl;
	return 0;
}