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