P1226 【模闆】快速幂||取餘運算 C++

日期：2021-04-24

作者：19屆WY

标簽：快速幂，同餘運算

題目描述

同餘運算的主要性質

解題：

1. 利用同餘運算的性質，可以每次将p進行二分取餘，若p為偶數，則xp=(x2)p/2,若p為奇數，則xp=x*(x2)p/2。
2. （考慮p>0的情況）每次将p/2，若p為奇數，則xp=x*(x2)p/2，中前面那個單獨的x也要取餘之後再放進s中，若p為偶數則直接計算x2再取餘，這裡不用再與s進行計算，因為最後一步總會得到p=1，結果都會進入s中
3. （考慮p=0的情況）最後輸出的時候要再取一次餘，舉例：若b=5,p=0,k=1,因為p=0是以不會進入循環，是以s沒有經過運算保持為1，但明顯結果應該為0，是以要再取一次餘
4. 注意一下b，p的值會被改變，是以存一下開始輸入的值

#include<iostream>
using namespace std;
int main(){
	long long b,p,k,i,a,c;
	cin >> b >> p >> k;
	a=b;
	c= p;
	long long s=1;
	while(p>0){
		if(p%2 == 1){
			s = s * b % k;
		}
		b = b * b % k;
		p = p / 2;
	}
	cout<<a<<"^"<<c<<" "<<"mod"<<" "<<k<<"="<<s%k;
} 


           

辣雞解法：

一開始想到的是直接遞歸，一直二分遞歸，沒有了解快速幂的思想，60分，逾時了

#include<iostream>
using namespace std;
long long mod(long long a,long long b, long long c);
int main(){
	long long b,p,k,i;
	cin >> b >> p >> k;
	long long s = mod(b,p,k);
	cout<<b<<"^"<<p<<" "<<"mod"<<" "<<k<<"="<<s;
	
} 

long long mod(long long a,long long b, long long c){
	int ans;
	if(b == 1)
	return a % c;
	return (mod(a, b/2, c) % c)* (mod(a, b - b/2, c) % c) % c;
}