快速幂运算

形如快速幂运算，一般用二进制优化加速。复杂度

这里举个例子来说明是如何加速的，例如。

将化成二进制，即 $，$ ，从右往左开始，首先将初始化为 1，令

第一位为 1 奇数位，做运算，即，然后自身平方一次，此时
第二位也为 1 奇数位，，此时，即，然后自身平方一次，
第三位为 0 偶数位，不做运算，但还是要自身平方一次，此时
第四位为 1 奇数位，做运算，即，即，运算结束，返回

实现代码（取模 mod）

typedef long long ll;
ll mod_pow(ll x, ll n, ll mod) {
	ll ret = 1;
	while(n) {
		if(n & 1)  ret = (ret * x) % mod; // 奇数位
		x = x*x%mod; // 每位都平方
		n >>= 1; // 右移
	}
	return ret;
}

习题

POJ 3641

题目地址：http://poj.org/problem?id=3641

题目大意

根据费马定理，对于素数和满足，若对于非素数，也有一些满足方程的话，则称为基于的伪素数，现给出，问是否为基于的伪素数。

思路

按照题意做即可，若非素数满足定理的话，即那就是伪素数了。运输量较大需要用到快速幂运算，并取模。

AC 代码

/*************************************************************************
	> File Name: 3641.cpp
	  > Author: Netcan
	  > Blog: http://www.netcan666.com
	  > Mail: 1469709759@qq.com
	  > Created Time: 2015-12-21 一 08:52:02 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

typedef long long ll;

ll a, p;

ll mod_pow(ll x, ll n, ll mod) {
	ll res = 1;
	while(n) {
		if(n&1) res = (res*x) % mod;
		x=x*x%mod;
		n>>=1;
	}
	return res;
}

ll is_prime(ll x) {
	if(x < 2) return false;
	if(x == 2) return true;
	for(ll i=3; i*i<=x; i+=2) if(x%i==0) return false;
	return true;
}

void solve() {
	if(is_prime(p)) {
		cout << "no" << endl;
		return;
	}
	cout << (mod_pow(a, p, p) == a?"yes":"no") << endl;
}

int main()
{
#ifdef Oj
	freopen("3641.in", "r", stdin);
#endif
	while(cin >> p >> a) {
		if(a==0 && p == 0) break;
		solve();
	}
	return 0;
}

POJ 1995

题目地址：http://poj.org/problem?id=1995

题目大意

求的值。

思路

快速幂运算并取模。

AC 代码

/*************************************************************************
	> File Name: 1995.cpp
	  > Author: Netcan
	  > Blog: http://www.netcan666.com
	  > Mail: 1469709759@qq.com
	  > Created Time: 2015-12-21 一 09:23:08 CST
 ************************************************************************/

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <sstream>
#include <deque>
#include <functional>
#include <iterator>
#include <list>
#include <map>
#include <memory>
#include <stack>
#include <set>
#include <numeric>
#include <utility>
#include <cstring>
using namespace std;

typedef long long ll;
int H, M;
ll A[45005], B[45005];

ll mod_pow(ll x, ll n, ll mod) {
	ll ret = 1;
	while(n) {
		if(n & 1)  ret = (ret * x) % mod;
		x = x*x%mod;
		n >>= 1;
	}
	return ret;
}

void solve() {
	ll ans = 0;
	for(int i=0; i<H; ++i) ans += mod_pow(A[i], B[i], M);
	ans %= M;
	cout << ans << endl;
}

int main()
{
#ifdef Oj
	freopen("1995.in", "r", stdin);
#endif
	int Z;
	cin >> Z;
	while(Z--) {
		cin >> M >> H;
		for(int i=0; i<H; ++i)
			cin >> A[i] >> B[i];
		solve();
	}
	return 0;
}