快速幂

问题

输入x,n,px, n, p，计算xn mod px ^ n \bmod p。

基本算法

一个暴力的做法就是直接把nn个xx乘起来，时间复杂度为O(n)O(n)

考虑一个递归的计算方法：
ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 27: …gin{cases} 1,&{\̲m̲b̲o̲x̲{如果}}n=0\\ x\,(…
每次递归nn都会变为原先的一半，所以时间复杂度为O(log⁡n)O(\log n)。

对于非递归的做法，考虑nn的二进制表示bkbk−1⋯ ,b0b_k b_{k-1} \cdots, b_0。
xn=bkx2k×bk−1x2k−1×⋯×b0x20x^n = b_k x^{2^k} \times b_{k-1} x^{2^{k-1}} \times \cdots \times b_0 x^{2^0}
对于x20,x21,…,x2kx^{2^0}, x^{2^1}, \ldots, x^{2^k}每一项是前面一项的平方，
可以在O(k)O(k)的时间内计算，然后再根据bib_i的值，
决定每个x2ix^{2^i}是否乘入答案中。

例子

x^1 = x
x^2 = x^1 * x^1 % p
x^4 = x^2 * x^2 % p
x^8 = x^4 * x^4 % p
x^16 = x^8 * x^8 % p
x^17 = x^1 * x^16 % p

代码

递归的实现

long long pow(long long x, long long n, long long p) {
    if (n == 0) {
        return 1;
    } else {
        int t = pow(x * x % p, n / 2, p);
        if (n % 2 == 1) {
            t = t * x % p;
        }
        return t;
    }
}

非递归的实现

int pow(int x, int n, int p) {
    int re = 1;
    for (; n > 0; n >>= 1) {
        if (n % 2 == 1) {
            re = (long long)re * x % p;
        }
        x = (long long)x * x % p;
    }
    return re;
}
  1. 一般使用非递归版本较多。
  2. 在数论和计数问题中，一般认为00=10^0 = 1.
  3. nn为负数，会导致程序出错。
  4. 如果p=1,n=0p = 1, n = 0，那么函数会返回11，而应该返回00，除了极少数坑人的题目，一般并不需要考虑这种情况。
  5. 如果pp的范围超过了int，那么需要额外实现一个long long * long long % long long 的函数，见推广部分。
  6. x可能大于p，在一些情况中，这会导致第一次x * x % p越界。
  7. 如果不考虑代码风格，可以把(n % 2 == 1)替换为(n & 1)。

其他语言

Python语言中的pow函数，可以直接计算整数的快速幂，非常适合用来做手速题。（其实你只需要在自己的模板中实现出快速幂即可）

推广

在一些情况中快速幂的nn可能非常大。

  1. 如果nn是输入的高精度数字（一般为十进制）那么并不需要进行每次模二，除以二的快速幂；可以用十进制快速幂。
  2. 如果是通过其他方式计算的，比如希望计算pow(x, pow(y, n), p)可以先通过找循环节的方式把指数部分取模pow(x, pow(y, n), p) == pow(x, pow(y, n, p - 1), p)

这个算法对于所有有结合律的运算均可以优化，其他常见的如下

  1. 整数
  2. 矩阵
  3. 多项式
  4. 排列/置换

题目

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

https://www.luogu.com.cn/problem/P1226

题目描述

给你三个整数 a,b,pa,b,p，求 ab mod pa^b \bmod p。

输入格式

输入只有一行三个整数，分别代表 a,b,pa,b,p。

输出格式

输出一行一个字符串 a^b mod p=s，其中 a,b,pa,b,p 分别为题目给定的值， ss 为运算结果。

样例 #1

样例输入 #1
2 10 9
样例输出 #1
2^10 mod 9=7

提示

样例解释

210=10242^{10} = 1024，1024 mod 9=71024 \bmod 9 = 7。

数据规模与约定

对于 100%100\% 的数据，保证 0≤a,b<2310\le a,b < 2^{31}，a+b>0a+b>0，2≤p<2312 \leq p \lt 2^{31}。

参考代码

#include <bits/stdc++.h>
using namespace std;

long long gao(long long b, long long p, long long k) {// b的p次方mod k
	if (p == 0) {
		return 1 % k;
	} else if (p % 2 == 0) {
		long long r = gao(b, p / 2, k);
		return r * r % k;
	} else {
		return gao(b, p - 1, k) * b % k;
	}
}
long long b, p, k;
int main() {
	cin >> b >> p >> k;
	printf("%lld^%lld mod %lld=%lld\n", b, p, k, gao(b, p, k));
	return 0;
}

题解

快速幂模板题，但是需要考虑很多特殊情况

越界和取模
int 2e9
long long 9e18

底数是1
底数是0
指数是0
指数是负数
模数是1

P6075 [JSOI2015]子集选取

https://www.luogu.com.cn/problem/P6075

题目描述

给定 nn 个元素的集合 S={ 1,2...n}S= \left\{ \ 1,2...n \right\} 和整数kk，现在要从SS 中选出若干子集 Ai,jA_{i,j}（A⊆SA \subseteq S，1≤j≤i≤k1 \le j \le i \le k）排成下面所示边长为 kk 的三角形（因此总共选出了 12k(k+1)\frac{1}{2} k(k+1) 个子集）。
A1,1A2,1A2,2A3,1A3,2A3,3⋮⋮⋮⋱Ak,1Ak,2Ak,3⋯Ak,k\begin{matrix} A_{1,1}\\ A_{2,1}&A_{2,2}\\ A_{3,1}&A_{3,2}&A_{3,3}\\ \vdots&\vdots&\vdots&\ddots\\ A_{k,1}&A_{k,2}&A_{k,3}&\cdots&A_{k,k} \end{matrix}

此外，JYY 对选出的子集之间还有额外的要求：选出的这些子集必须满足
Ai,j⊆Ai,j−1A_{i,j} \subseteq A_{i,j-1} 且 Ai,j⊆Ai−1,jA_{i,j} \subseteq A_{i-1,j}。
JYY 想知道，求有多少种不同的选取这些子集的方法。因为答案很大，JYY 只关心输出答案模 1,000,000,0071,000,000,007 的值。

对于两种选取方案 A={ A1,1,A2,1,Ak,k}A = \left\{ \ A_{1,1} , A_{2,1} , A_{k,k} \right\} 和 B={ B1,1,B2,1,Bk,k}B = \left\{ \ B_{1,1} , B_{2,1} , B_{k,k} \right\} 只要存在 i,ji,j 满足 Ai,j≠Bi,jA_{i,j} \neq B_{i,j}，我们就认为 AA 和 BB 是不同的方案。

输入格式

输入包含一行两个整数 nn 和 kk。

输出格式

一行一个整数，表示不同方案数目模 1,000,000,0071,000,000,007 的值。

样例 #1

样例输入 #1
2 2
样例输出 #1
16

提示

对于 100%100\% 的数据，1≤n1 \le n，k≤109k \le 10^9。

参考代码

题解

P3197 [HNOI2008]越狱

https://www.luogu.com.cn/problem/P3197

题目描述

监狱有 nn 个房间，每个房间关押一个犯人，有 mm 种宗教，每个犯人会信仰其中一种。如果相邻房间的犯人的宗教相同，就可能发生越狱，求有多少种状态可能发生越狱。

答案对 100,003100,003 取模。

输入格式

输入只有一行两个整数，分别代表宗教数 mm 和房间数 nn。

输出格式

输出一行一个整数代表答案。

样例 #1

样例输入 #1
2 3
样例输出 #1
6

提示

样例输入输出 1 解释

状态编号 1 号房间 2 号房间 3 号房间
1 信仰 1 信仰 1 信仰 1
2 信仰 1 信仰 1 信仰 2
3 信仰 1 信仰 2 信仰 2
4 信仰 2 信仰 1 信仰 1
5 信仰 2 信仰 2 信仰 2
6 信仰 2 信仰 2 信仰 1

数据规模与约定

对于 100%100\% 的数据，保证 1≤m≤1081 \le m \le 10^8，1≤n≤10121 \le n \le 10^{12}。

参考代码

#include <bits/stdc++.h>
using namespace std;
long long n, m, p = 100003;
long long pw(long long x, long long y, long long p) {
	long long re = 1;	
	for (; y; y >>= 1) {
		if (y & 1) {
			re = re * x % p;
		}
		x = x * x % p;
	}
	return re;
}
int main() {
	cin >> m >> n;
	long long a = pw(m, n, p);
	long long b = pw(m - 1, n - 1, p) * m % p;
	cout << (a + p - b) % p << endl;
}

题解

全部减去不会发生越狱的。

(pow(m, n, mod) - pow(m - 1, n - 1, mod) * m) % mod

https://en.wikipedia.org/wiki/Greatest_common_divisor
int gcd(int x, int y) {
return y ? gcd(y, x % y) : x;
}

int lcm(int x, int y) {
return x / gcd(x, y) * y;
}

P1965 [NOIP2013 提高组] 转圈游戏

https://www.luogu.com.cn/problem/P1965

题目描述

nn 个小伙伴（编号从 00到 n−1n-1）围坐一圈玩游戏。按照顺时针方向给 nn个位置编号，从00 到 n−1n-1。最初，第 00号小伙伴在第 00号位置，第 11号小伙伴在第 11 号位置，……，依此类推。游戏规则如下：每一轮第 00 号位置上的小伙伴顺时针走到第mm 号位置，第 11号位置小伙伴走到第 m+1m+1 号位置，……，依此类推，第n - m号位置上的小伙伴走到第 0 号位置，第n∼m+1n \sim m+1 号位置上的小伙伴走到第11 号位置，……，第n−1n-1 号位置上的小伙伴顺时针走到第m−1m-1 号位置。

现在，一共进行了 10k10^k轮，请问xx 号小伙伴最后走到了第几号位置。

输入格式

共11行，包含 44 个整数n,m,k,xn,m,k,x，每两个整数之间用一个空格隔开。

输出格式

11个整数，表示 10k10^k轮后 xx 号小伙伴所在的位置编号。

样例 #1

样例输入 #1
10 3 4 5
样例输出 #1
5

提示

对于 30%30\%的数据，0<k<70 < k < 7；

对于 80%80\%的数据，0<k<1070 < k < 10^7；

对于100%100\%的数据，1<n<1,000,000,0<m<n,1≤x≤n,0<k<1091 <n < 1,000,000,0 < m < n,1 ≤ x ≤ n,0 < k < 10^9。

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, m, k, x;
long long pw(long long x, long long y, long long p) {
	long long re = 1;	
	for (; y; y >>= 1) {
		if (y & 1) {
			re = re * x % p;
		}
		x = x * x % p;
	}
	return re;
}
int main() {
	cin >> n >> m >> k >> x;
	cout << (x + m * pw(10, k, n)) % n << endl;
}

题解

spoj NDT

参考资料

Wikipedia Exponentiation by squaring

  1. 快速幂
    1. 问题
    2. 基本算法
    3. 例子
    4. 代码
    5. 其他语言
    6. 推广
    7. 题目
      1. P1226 【模板】快速幂||取余运算
      2. P6075 [JSOI2015]子集选取
      3. P3197 [HNOI2008]越狱
      4. P1965 [NOIP2013 提高组] 转圈游戏
      5. spoj NDT
    8. 参考资料
≡