欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

快速幂取模

程序员文章站 2022-07-09 10:26:53
...

模板一:

long long Mode(long long a, long long b, long long mode){
	long long sum = 1;
	a = a % mode;
	while (b > 0) {
		if (b % 2 == 1)		//判断是否是奇数,是奇数的话将多出来的数事先乘如sum
			sum = (sum * a) % mode;
		b /= 2;
		a = (a * a) % mode;// 不断的两两合并再取模,减小a和b的规模
	}
	return sum;
}

模板二:【位操作】

long long Mode(long long a, long long b, long long mode){
	long long sum = 1;
	while (b) {
		if (b & 1) {
			sum = (sum * a) % mode;
			b--;
		}
		b /= 2;
		a = a * a % mode;
	}
	return sum;
}

 

相关标签: 快速幂取模