快速幂

[编程题]快速幂

热度指数：262 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 128M，其他语言256M
算法知识视频讲解

求 $a^n\ \mathbb{mod}\ P$ 。

输入描述:

输入一行，三个整数a,n,P（）。

输出描述:

输出 $a^n\ \mathbb{mod}\ P$ 。

示例1

输入

2 3 100

输出

示例2

输入

3 100000 10000

输出

算法知识视频讲解

一切都会好起来的吧

#include<bits/stdc++.h>
using namespace std;
int main(){
	int a,n,p;
	cin>>a>>n>>p;
	int res=1;
	while(n){
		if(n&1){
			res=res*a%p;
		}
		a=a*a%p; 
		n>>=1;
	}
	cout<<res<<endl;
}

快速幂模板

发表于 2020-03-18 15:49:08 回复(0)

C/C++

猫猫猫1

#include<bits/stdc++.h>
using namespace std;

int F(int a,int n,int p) {
    int answer=1;
    while(n!=0){
        if(n%2==1){
            answer*=a;
            answer%=p;
        }
        n/=2;
        a*=a;
        a%=p;
    }
    return answer;
}

int main() {
    int a,n,p;
    while(cin>>a>>n>>p) {
        cout<<F(a,n,p)<<endl;
    }
    return 0;
}

发表于 2022-10-08 21:14:21 回复(0)

讲原则的柯基在创作

//c++快速幂模板

#include <iostream>

using namespace std;
long long qmi(long long a,long long b,long long p){
int res=1;
while(b){
if(b&1)res=res*a%p;
b>>=1;
a=a*a%p;
}
return res;
}
int main() {
long long a,b,p;
cin>>a>>b>>p;
cout<<qmi(a,b,p);
}

发表于 2023-04-17 20:28:30 回复(0)