快速幂

两个基础公式： \[ x\%p\%p\cdots\%p=x\%p \]

\[ (x \Lambda y) \% p = \{(x \% p) \Lambda (y \% p)\} \% p \]

这里\(\Lambda\)可以是+ - *。

求解下面的问题： \[ x^n \% p = ? \] 普通算法：

uint64_t m_pow_n_mod(uint64_t x, uint64_t n, uint64_t p)
{
	uint64_t r = 1;
	while (n > 0)
	{
		 // (x * x) % p = ((x % p) * (x % p)) % p
		r %= p;
		r *= x;
		--n;
	}
	return r % p;
}

快速幂算法：

uint64_t m_fast_pow_n_mod(uint64_t x, uint64_t n, uint64_t p)
{
	uint64_t r = 1;
	while (n > 0)
	{
		//r * x % p 
		if (n & 1)
		{
			r %= p;
			r *= x;
			r %= p;
		}
		// x * x % p
		x %= p;
		x *= x;
		x %= p;
		n >>= 1;
	}
	return r % p;
}

这里我写了一个含返回值的测试目标函数执行时间的函数：（C++ 14）

#include <time.h>		// time_t, clock
#include <algorithm>    // std::forward

template<typename T>
struct m_ret_type
{
	T data;
	double time_ms{ 0.0 };
	double time_s{ 0.0 };

	m_ret_type(const T& _data, const double _time_ms, const double _time_s)
		noexcept:data(_data), time_ms(_time_ms), time_s(_time_s){}
};

template<typename Fn, typename... Args>
auto m_cal_time_with_return(Fn& fn, Args&&... args)
{
	time_t t1 = clock();
	auto _tmp = fn(std::forward<Args>(args)...);
	time_t t2 = clock();
	return m_ret_type<decltype(_tmp)>
	(
		_tmp,
		static_cast<double>(t2) - static_cast<double>(t1),
		(static_cast<double>(t2) - static_cast<double>(t1)) / CLOCKS_PER_SEC
	);
}

测试代码如下：

auto r1 = m_cal_time_with_return(m_pow_n_mod, 19, 1000000000, 1239001);
auto r2 = m_cal_time_with_return(m_fast_pow_n_mod, 19, 1000000000, 1239001);
cout << "time of no fast: " << r1.time_ms<< " ms" << endl;
cout << "time of using fast: " << r2.time_ms << " ms" << endl;
cout << r1.data << endl;
cout << r2.data << endl;

执行结果：（效率差距很大）

time of no fast: 6921 ms

time of using fast: 0 ms

809167

809167