快速幂运算

形如$x^n$快速幂运算,一般用二进制优化加速。复杂度$O(log_2 n)$

这里举个例子来说明是如何加速的,例如$x^n=2^{11}$。

将$n=11$化成二进制,即$n=(1011)_2,2^3+2^1+2^0 = 11$,从右往左开始,首先将$ret$初始化为1,令$x_0=x$

  1. 第一位为1奇数位,做$ret = ret\times x$运算,即$ret = \color{red}{1}\times \color{blue}{x_0}=2$,然后$x$自身平方一次,此时$x=x^2=4=\color{blue}{x_0^2}$
  2. 第二位也为1奇数位,$ret = ret \times x$,此时$ret = \color{red}{ret} \times x = \color{red}{x_0} \times \color{blue}{x_0^2} = \color{red}{2}\times \color{blue}{x_0^2} = \color{red}{2}\times \color{blue}{4} = 8$,即$ret=\color{red}{x_0^3}$,然后$x$自身平方一次,$x=x^2=16=\color{blue}{x_0^4}$
  3. 第三位为0偶数位,不做$ret = ret\times x$运算,但$x$还是要自身平方一次,此时$x=x^2=256=\color{blue}{x_0^8}$
  4. 第四位为1奇数位,做$ret = ret\times x$运算,即$ret = \color{red}{ret} \times x = \color{red}{x_0^3} \times \color{blue}{x_0^8} = \color{red}{8}\times \color{blue}{256} = 2048$,即$ret=\color{red}{x_0^{11}}$,运算结束,返回$ret$

实现代码(取模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

题目大意

根据费马定理,对于素数$p$和$a>1$满足$a^p = a\pmod p$,若对于非素数$p$,也有一些$a$满足方程的话,则称$p$为基于$a$的伪素数,现给出$p, a$,问$p$是否为基于$a$的伪素数。

思路

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

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

题目大意

求$(A_1^{B_1}+A_2^{B_2}+ ... +A_H^{B_H})\bmod M$的值。

思路

快速幂运算并取模。

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;
}