C/C++教程

P1226 【模板】快速幂||取余运算 C++

本文主要是介绍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;
}
这篇关于P1226 【模板】快速幂||取余运算 C++的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!