数学专题：同余定理、gcd与lcm、中位数定理、筛法、快速幂等
文章目录
Java中数学相关的库函数
Math类提供了一系列数学方法，这里列了两个不常用的
| 方法 | 描述 |
|---|---|
| Math.sin(弧度) | 求sin值，参数为弧度而不是角度 |
| Math.PI | PI值 |
同余定理
原理
(a±b)%mod = (a%mod±b%mod)%mod
(a*b)%mod = (a%mod*b%mod)%mod
当计算结果太大，计算机无法表示时，题目会让我们对这个数取模再输出。但如果在计算这个数的过程中，中间结果就已经非常大，计算机无法表示时，这时该怎么办？此时同余定理就登场了，只要最终结果是由加减或乘法运算得到的，那么在每一步计算中我们都可以进行取模，最终的结果不变。
例题
解题思路
对于无法用long类型表示的非常大的数，我们一般都是用字符串表示，对于该题，最终我们还是需要将字符串变为数字，这时我们需要知道将字符串变为数字的方法
一般的想法是将字符串从后向前遍历，将数字的每位乘以其权重，如"12345" = 5 * 10 ^ 0 + 4 * 10 ^ 1 + 3 * 10 ^ 2 ...。但实际上我们从前向后遍历更快，也更易编写程序，我们使用ans表示转换后得到的数字，其初值为0，每遍历到一个字符，我们将ans * 10 + 当前字符表示的数字。例如”12345″的处理过程为：
s=12345
ans = 0 * 10 + 1 1 % p
ans = 1 * 10 + 2 12 % p
ans = 12 * 10 + 3 123 % p
...
这样，最终的数字是由乘法和加法运算得到的，利用同余定理，我们可以在每一小步都进行取余操作，这样中间结果也不会溢出，最终将得到的数字取余即可
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
String N;
long p, num;
int i;
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()) {
N = scanner.next();
p = scanner.nextLong();
num = 0;
for (i = 0;i < N.length();i++) {
num = ((num * 10 % p) + (N.charAt(i) - '0')) % p;
}
System.out.println(num);
}
}
}
gcd与lcm
原理
gcd表示最大公约数，lcm表示最小公倍数，a和b的最小公倍数等于a * b / gcd(a,b)，因此只要能求最大公约数，最小公倍数也能求得
求最大公约数的方法为辗转相除法，具体做法为：用较大数除以较小数，再用较小数（除数）除以出现的余数(第一余数)，再用第一余数除以出现的余数(第二余数)，如此反复，直到最后余数是0为止。如果是求两个数的最大公约数，那么最后的除数就是这两个数的最大公约数。
比如说:计算15和36的最大公约数。用辗转相除法是这么计算的：
36÷15=2······6 (第一余数)
15÷6=2······3 (第二余数)
6÷3=2······0(第三余数)
最终结果为3
用符号来表示，即：
a ÷ b = a / b ... a % b
接下来令 a = b，b = a % b，再执行上述公式，以此类推，
直到a % b == 0，此时b即为最大公约数
用递归式来表示，即：
gcd(a,b) = gcd(b, a % b)
注意a,b的大小顺序是不用考虑的，若a小b大，执行一次后又会换回来，例如15 ÷ 36 = 0 ... 15，第二步变成36 ÷ 15 = 2 ... 6，即又换了回来
gcd的算法程序如下：
int gcd(int a, int b) {
int c;
while (b != 0) {
c = a % b;
a = b;
b = c;
}
return a;
}
例题
解题思路
多个数的最小公倍数，就相当于不断求两个数间的最小公倍数
LCM(a1,a2,a3) = LCM(LCM(a1,a2),a3)
…
LCM(a1,a2,…,an) = LCM(LCM(LCM(a1,a2),a3)…)
lcm(a,b) = a * b / gcd(a, b)
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
long num, t, n, i, j, g = 1;
long m = 1;
Scanner scanner = new Scanner(System.in);
t = scanner.nextLong();
for (i = 0;i < t;i++) {
m = 1;
n = scanner.nextLong();
for (j = 0;j < n;j++) {
num = scanner.nextInt();
m = m * num / (gcd(m, num));
}
System.out.println(m);
}
}
static long gcd(long a, long b) {
long c;
while (b != 0) {
c = a % b;
a = b;
b = c;
}
return a;
}
}
容斥原理
原理
两个集合的容斥关系公式：|A∪B| = |A|+|B| – |A∩B |(∩：重合的部分）
三个集合的容斥关系公式：|A∪B∪C| = |A|+|B|+|C| – |A∩B| – |B∩C| – |C∩A| + |A∩B∩C|
奇加偶减。
例题
解题思路
利用容斥原理即可，注意1 ~ n中能被a整除的数的个数就是n / a，而能被a和b同时整数的数，即为能被a和b的最小公倍数整除的数
代码
import java.util.*;
public class Main {
public static void main(String[] args) {
long n, a, b, c, abNum, acNum, bcNum, abcNum;
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextLong()) {
n = scanner.nextLong();
a = scanner.nextLong();
b = scanner.nextLong();
c = scanner.nextLong();
long ans = 0;
ans += n / a + n / b + n / c;
ans -= n / (a * b / gcd(a, b)) + n / (a * c / gcd(a, c)) + n / (b * c / gcd(b, c));
ans += n / (a * b * c / gcd(gcd(a, b), c));
System.out.println(ans);
}
}
static long gcd(long a, long b) {
long c;
while (b != 0) {
c = a % b;
a = b;
b = c;
}
return a;
}
}
中位数定理、曼哈顿距离
原理
中位数定理：
曼哈顿距离：
在平面上，坐标(x1,y1)的i点与坐标(x2,y2)的j点的曼哈顿距离为：d(i,j)=|X1-X2|+|Y1-Y2|
对于坐标平面上的两个点，若要从一个点到另一个点，只能上、下、左、右四个方向进行移动，则两点之间的曼哈顿距离就是两点之间的最短距离，即最短距离与选取什么路线，怎么移动无关，只取决于初始位置。曼哈顿距离可以让我们忽略具体的移动方案，而只关注起点与终点。
例题
解题思路
士兵的移动符合曼哈顿距离的移动规则，根据曼哈顿距离的性质，我们可以不用考虑士兵是如何具体移动的，同一时刻任一网格点上只能有一名士兵，士兵的移动是否会撞在一个点上，这些我们都可以不考虑，因为总能找到不碰撞的行进方案，只要起终点一样，最终计算的距离结果就一样。
我们可以用曼哈顿距离公式计算士兵的起始与终止点的距离，因此我们分行与列两方面考虑。设y1,y2,…,yn表示排序后的士兵起始行号，最后士兵都排到同一行y上，在行方向的行进距离为|y1 - y| + |y2 - y| + ... + |yn - y|，我们要求上式的最小值，这时中位数定理就登场了，当y为士兵初始位置行y1,y2,…,yn中的中位数时，上式最小。
再考虑列的情况，设x1,x2,…,xn表示排序后的士兵起始列号，注意到最终每个士兵都是紧挨着的，与相邻士兵的距离都为1，设最终位置为x,x + 1,x + 2,...,x + n - 1，那么在列方向的行进距离为|x1 - x| + |x2 - (x + 1)| + ... + |xn - (x + n - 1)|，化简上式为|x1 - x| + |x2 - 1 - x| + ... + |xn - n + 1 - x|，这时我们就能看出来了，利用中位数定理，当x为x1,x2 - 1,x3 - 2,...,xn - n + 1的中位数时，上式最小
对士兵位置进行排序，按上述思路计算曼哈顿距离即可求得答案
代码
import java.util.*;
public class Main {
static int[] xlist = new int[10002];
static int[] ylist = new int[10002];
public static void main(String[] args) {
int n, x, y, i, ans;
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
n = scanner.nextInt();
ans = 0;
for (i = 0;i < n;i++) {
x = scanner.nextInt();
y = scanner.nextInt();
xlist[i] = x;
ylist[i] = y;
}
Arrays.sort(ylist, 0, n);
for (i = 0;i < n;i++) {
ans += Math.abs(ylist[i] - ylist[n / 2]);
}
Arrays.sort(xlist, 0, n);
for (i = 0;i < n;i++) {
xlist[i] -= i;
}
Arrays.sort(xlist, 0, n);
for (i = 0;i < n;i++) {
ans += Math.abs(xlist[i] - xlist[n / 2]);
}
System.out.println(ans);
}
}
}
筛法
原理
这里的筛法指的是使用埃筛的思路进行解题，不一定是求素数，也可以用于其他方面，是指一种预处理和打表的思想。筛法（挨拉托色尼筛法）可以用来求所有小于N的素数。把从2（素数是指大于1的自然数）开始的某一范围内的正整数从小到大按顺序排列，逐步筛掉非素数留下素数。用筛法求素数的基本思想是：把从2到N的一组正整数从小到大按顺序排列。从中依次删除2的倍数、3的倍数、4的倍数，直到根号N的倍数为止，剩余的即为2~N之间的所有素数（这里没有做优化）
例题
解题思路
使用筛法的思想，获取1000000内的所有素数，可以将其存放在一个ArrayList中，然后使用双指针同时遍历即可，头指针从前往后遍历，尾指针从后往前遍历，找到所有满足条件的组合
代码
import java.util.*;
public class Main {
static int[] table = new int[1000002];
static List<Integer> prime = new ArrayList<>();
public static void main(String[] args) {
int i, j, n;
for (i = 2;i <= Math.sqrt(1000000);i++) {
j = i * i;
while (j <= 1000000) {
table[j] = 1;
j += i;
}
}
for (i = 2;i <= 1000000;i++) {
if (table[i] == 0) {
prime.add(i);
}
}
Scanner scanner = new Scanner(System.in);
while (scanner.hasNextInt()) {
n = scanner.nextInt();
for (i = 0, j = prime.size() - 1;i <= j;) {
if (prime.get(i) + prime.get(j) == n) {
System.out.println(prime.get(i) + " " + prime.get(j));
i++;
j--;
}else if (prime.get(i) + prime.get(j) < n){
i++;
} else {
j--;
}
}
System.out.print('\n');
}
}
}
快速幂
原理
引入: 大家如何求 a ^ b??普通做法: 循环一遍每次乘a。若我们要求a^b,按照朴素算法就是把a连乘b次，这样一来时间复杂度是O(b)也即是O(n)级别。
而快速幂能做到O(logn)，原理如下：
假设我们要求a ^ b，那么其实b是可以拆成二进制的，该二进制数第i位的权为2 ^ (i-1)，例如当b==11时，a ^ 11=a ^ (2 ^ 0+2 ^ 1+2 ^ 3)=a ^ (2 ^ 0) * a ^ (2 ^ 1) * a ^ (2 ^ 3)。11的二进制是1011，11 = 2 ^ 3×1 + 2 ^ 2×0 + 2 ^ 1×1 + 2 ^ 0×1，因此，我们将a^11转化为算a ^ (2 ^ 0) * a ^ (2 ^ 1) * a ^ (2 ^ 3)
根据上述快速幂与二进制的关系，对于a ^ b，我们用ans表示最终结果，初值为1，用base表示每一位的权，初值为a，对于b的每一位对应的权，从后到前，分别对应a ^ 1，a ^ 2，a ^ 4，a ^ 8...，从后往前遍历b的二进制位，若当前位为1，则ans = ans * base，遍历当前位后，base = base * base，更新为下一位的权，依次类推。我们使用右移和&1操作判断b的每一位是否为1，算法代码如下：
long fastPow(long a, long b) {
long ans = 1, base = a;
while (b != 0) {
if ((b & 1) == 1) {
ans *= base;
}
base *= base;
b >>= 1;
}
return ans;
}
例题
解题思路
快速幂即可，注意N为负数的情况，答案即为1 / fastPow(x, (-1) * N)
需要注意的是，题目n范围中最小为-2 ^ 31，fastPow的第二个参数必须为long类型，不能为int类型，因为乘以-1后，2 ^ 31 int类型无法表示
代码
class Solution {
public double myPow(double x, int n) {
if (x == 1) {
return (double)1;
}
long N = (long)n;
return N < 0 ? 1 / fastPow(x, (-1) * N) : fastPow(x, N);
}
public double fastPow(double a, long b) {
double ans = 1;
while (b != 0) {
if ((b & 1) == 1) {
ans = (ans * a);
}
a = (a * a);
b >>= 1;
}
return ans;
}
}
组合数学
原理
这里主要介绍求组合数的公式：C[0][0] = 1, C[n][m] = C[n-1][m]+C[n-1][m-1]
利用上式，我们可以开一个二维数组来求组合数，需注意C[i][0] = C[i][i] = 1
组合数公式的证明：
1.将C(n,m)理解为在n个物体中取m个物体的方案总数；
2.现在将n个物体分成一号堆n-1个物体和二号堆1个物体；
3.n个物体的二号堆只有1个物体，分为取和不取两种情况；
4.若取，则从一号堆的n-1个物体中取出m-1个物体，为C(n-1,m-1)；
5.若不取，则从一号堆的n-1个物体中取出m个物体，为C(n-1,m)；
6.因此，C(n,m)的方案总数为C(n-1,m-1)和C(n-1,m)的总和；
例题
解题思路
可以推出要求的系数为C[k][t1]*C[k-t1][t2]*a ^ t1*b ^ t2*c ^ t3，用二维数组求组合数，加上快速幂即可求解
代码
import java.util.*;
public class Main {
static long m = 1000000000 + 7;
static long[][] Comb = new long[1002][1002];
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
long ans = 1, a, b, c;
int i, j, k, t1, t2, t3;
a = scanner.nextLong();
b = scanner.nextLong();
c = scanner.nextLong();
k = scanner.nextInt();
t1 = scanner.nextInt();
t2 = scanner.nextInt();
t3 = scanner.nextInt();
ans = ans * fastPow(a, t1);
ans = ans * fastPow(b, t2) % m;
ans = ans * fastPow(c, t3) % m;
for (i = 0;i < 1002;i++) {
Comb[i][0] = 1;
Comb[i][i] = 1;
for (j = 1;j < i;j++) {
Comb[i][j] = (Comb[i - 1][j] + Comb[i - 1][j - 1]) % m;
}
}
ans = ans * Comb[k][t1] % m;
ans = ans * Comb[k - t1][t2] % m;
System.out.println(ans);
}
static long fastPow(long a, long b) {
long result = 1, base = a;
while(b != 0) {
if ((b & 1) == 1) {
result = result * base % m;
}
b = b >> 1;
base = base * base % m;
}
return result;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/153743.html
