【蓝桥杯省赛】冲刺练习题【数学公式】倒计时【06】

2022-11-29 21:07:50 浏览数 (3)

目录

1、判断质数

2、分解质因数

3、快速幂

3、欧几里得定力

4、海伦公式（求三角形面积）

5、排列数公式

排列数:

排列数公式

符号

推导过程

示例：

附加1：矩阵相乘

附加2：线性同余方程(B组以上)

理论示例：

代码示例：

青蛙的约会

1、判断质数

质数又称为素数，是指大于1的并且除了1和它本身外，没有其他因数的自然数。

判断一个数是否是质数 假设该数为n， 我们只需要判断

内是否有n的因子。如果有，则n为合数，否则，n为质数。

这种方法被称为试除法， 即试着除一下所有可能的因子。

代码语言：javascript复制
package action;

public class demo {
	public static void main(String[] args) {
		System.out.println(isf(5));;
	}
	public static Boolean isf(int n){
	    if(n == 1) return false;
	    for(int i = 2; i <= n / i; i  ){
	        if(n % i == 0){
	            return false;
	        }
	    }
	    return true;
	}
}

​

2、分解质因数

根据算术基本定理又称唯一分解定理，对于任何一个合数， 我们都可以用几个质数的幂的乘积来表示。

​

接下来我们利用这个公式分解质因数。 设一个质数为p.如果n%p == 0，那么p就是n的一个质因数，接下来就是求p的指数，我们让n = n/p, 这样就从n中剔除了一个p,接着重复上述两步，直到n%p ！= 0

代码语言：javascript复制
package action;

public class demo {
	public static void main(String[] args) {
		isf(500);
	}
	public static void isf(int n) {
		for (int i = 2; i <= n / i; i  ) {
			int a = 0, b = 0;
			while (n % i == 0) {
				a = i;
				n /= i;
				b  ;
			}
			if (b > 0) {
				System.out.println(a   " "   b);
			}
		}
		if (n > 1) {
			System.out.println(n   " "   1);
		}
	}
}

​

3、快速幂

当我们计算

时，常用的做法是对n连乘k次， 但如果k特别大，假如k = 1e6， 如果仍然对n连乘1e6次的话，时间消耗就太大了。那么我们如何在短时间内求出一个数的k次方呢。

求

​

快速幂

​

没有处理超大数

代码语言：javascript复制
package action;

public class demo {
	public static void main(String[] args) {
		System.out.println(ksm(2, 10));
	}

	public static int ksm(int a, int b) { // 求 a^b
		int res = 1; // res保存结果
		while (b != 0) {
			if ((b & 1) == 1) { // 如果k的二进制数的最后一位是 1。 比如1011 & 1 = 1
				res = (res * a);
			}
			a = a * a;// 得到 a^1, a^2, a^4, a^8, .....
			b = b >> 1; // 将b右移一位，去掉最低位。为了开始判断下一位。
		}
		return res;
	}

}

3、欧几里得定力

最大公约数、最小公倍数

代码语言：javascript复制
package Action;
 
public class demo {
	/*
	 * 求最大公约数 最小公倍数 思路：根据欧几里得定理 gcd(a,b)=gcd(b,a%b);
	 */
	static int gcd(int a, int b) {
		// 出口：b=0;5和0的最大公约数是5
		if (b == 0)
			return a;
		return gcd(b, a % b);
	}
 
	static int lcm(int a, int b) {
		return a * b / gcd(a, b);
	}
 
	public static void main(String[] args) {
		System.out.println(gcd(45, 35));
		System.out.println(lcm(45, 35));
		System.out.println(gcd(42, 60));
		System.out.println(lcm(42, 60));
	}
}

4、海伦公式（求三角形面积）

5、排列数公式

排列数公式就是从n个不同元素中，任取m（m≤n）个元素（被取出的元素各不相同），按照一定的顺序排成一列，叫做从n个不同元素中取出m个元素的一个排列。排列与元素的顺序有关，组合与顺序无关。加法原理和乘法原理是排列和组合的基础。

排列数:

从n个不同的元素中任取m(m≤n)个元素的所有排列的个数，叫做从n个不同的元素中取出m(m≤n)个元素的排列数。记作符号

 。A是英文arrangement（排列）的第一个大写字母。

例如，从7个不同的元素中任取5个元素的排列数为

 ，从10个不同的元素中任取7个元素的排列数为

。

排列数公式

 公式A是排列公式，从N个元素取M个进行排列（即排序）。

符号

C：组合数 A：排列数（在旧教材为P） N：元素的总个数 M：参与选择的元素个数 !：阶乘，如5！=5×4×3×2×1=120 C：Combination 组合 P：Permutation排列 (现在教材为A-Arrangement)

推导过程

求排列数

可以按依次填m个空位来考虑：假定有排好顺序的m个空位,从n个不同元素a1,a2,a3,…,an中任意取m个去填空,一个空位填1个元素，每一种填法就对应1个排列，因此，所有不同填法的种数就是排列数。

填空可分为m个步骤：

第1步，第1位可以从n个元素中任选一个填上，共有n种填法；

第2步，第2位只能从余下的n-1个元素中任选一个填上，共有n-1种填法；

第3步，第3位只能从余下的n-2个元素中任选一个填上，共有n-2种填法；

……

第m步，当前面的m-1个空位都填上后，第m位只能从余下的n-(m-1)个元素中任选一个填上，共有n-m 1种填法。

根据分步计数原理，全部填满m个空位共有n(n-1)(n-2)…(n-m 1)种填法。所以得到公式：

 这里n，m∈N*，并且m≤n这个公式叫做排列数公式其中，公式右边第一个因数是n，后面的每个因数都比它前面一个因数少1，最后个因数为n-m 1，共有m个因数相乘。

排列数公式还可以写成：

注意：为了保证公式在n=m时成立，特规定0! =1。

示例：

在10个球中，任意取3个（不放回），求有多少种取法？

代码语言：javascript复制
package action;

public class demo2 {
	public static void main(String[] args) {
		// 在10个球中，取3个(不放回)
		System.out.println(f(10) / f(10 - 3));
	}

	public static int f(int n) {
		if (n <= 1)
			return 1;
		return f(n - 1) * n;
	}
}

附加1：矩阵相乘

资源限制

内存限制：256.0MB   C/C 时间限制：1.0s   Java时间限制：3.0s   Python时间限制：5.0s

问题描述

　　小明最近在为线性代数而头疼，线性代数确实很抽象（也很无聊），可惜他的老师正在讲这矩阵乘法这一段内容。 　　当然，小明上课打瞌睡也没问题，但线性代数的习题可是很可怕的。 　　小明希望你来帮他完成这个任务。 　　现在给你一个ai行aj列的矩阵和一个bi行bj列的矩阵， 　　要你求出他们相乘的积（当然也是矩阵）。 　　(输入数据保证aj=bi,不需要判断)

输入格式

　　输入文件共有ai bi 2行，并且输入的所有数为整数（long long范围内）。 　　第1行：ai 和 aj 　　第2~ai 2行：矩阵a的所有元素 　　第ai 3行：bi 和 bj 　　第ai 3~ai bi 3行：矩阵b的所有元素

输出格式

　　输出矩阵a和矩阵b的积（矩阵c) 　　（ai行bj列）

样例输入

代码语言：javascript复制
2 2
12 23
45 56
2 2
78 89
45 56

样例输出

代码语言：javascript复制
1971 2356
6030 7141
代码语言：javascript复制
package action;

import java.io.IOException;
import java.util.Scanner;

public class demo2 {
	public static void main(String[] args) throws IOException {
		Scanner sc=new Scanner(System.in);
		String[] line1 = sc.nextLine().split(" ");
		int row1 = Integer.parseInt(line1[0]);
		int column1 = Integer.parseInt(line1[1]);

		int[][] m1 = new int[row1][column1];
		for (int i = 0; i < m1.length; i  ) {
			String[] data = sc.nextLine().split(" ");
			for (int j = 0; j < m1[i].length; j  ) {
				m1[i][j] = Integer.parseInt(data[j]);
			}
		}

		String[] line2 = sc.nextLine().split(" ");
		int row2 = Integer.parseInt(line2[0]);
		int column2 = Integer.parseInt(line2[1]);

		int[][] m2 = new int[row2][column2];
		for (int i = 0; i < m2.length; i  ) {
			String[] data = sc.nextLine().split(" ");
			for (int j = 0; j < m2[i].length; j  ) {
				m2[i][j] = Integer.parseInt(data[j]);
			}
		}
		sc.close();

		int[][] result = new int[105][105];
		for (int i = 0; i < row1; i  ) {
			for (int j = 0; j < column2; j  ) {
				for (int k = 0; k < row2; k  ) {
					result[i][j]  = m1[i][k] * m2[k][j];
				}
			}
		}

		for (int i = 0; i < row1; i  ) {
			for (int j = 0; j < column2; j  ) {
				if (j == column2 - 1) {
					System.out.println(result[i][j]);
				} else {
					System.out.print(result[i][j]   " ");
				}
			}
		}
	}
}

 ​​​​

附加2：线性同余方程(B组以上)

数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次.

在数论中，线性同余方程是最基本的同余方程，“线性”表示方程的未知数次数是一次，即形如：

ax≡b (mod n)的方程。

此方程有解当且仅当 b 能够被 a 与 n 的最大公约数整除（记作 gcd(a,n) | b）。

这时，如果 x0 是方程的一个解，那么所有的解可以表示为：

代码语言：javascript复制
{x0 kn/d|(k∈z)}

其中 d 是a 与 n 的最大公约数。在模 n 的完全剩余系 {0,1,…,n-1} 中，恰有 d 个解。

理论示例：

在方程3x ≡ 2 (mod 6)中， d = gcd(3,6) = 3 ，3 不整除 2，因此方程无解。 在方程5x ≡ 2 (mod 6)中， d = gcd(5,6) = 1，1 整除 2，因此方程在{0,1,2,3,4,5} 中恰有一个解: x=4。 在方程4x ≡ 2 (mod 6)中， d = gcd(4,6) = 2，2 整除 2，因此方程在{0,1,2,3,4,5} 中恰有两个解: x=2 and x=5。

代码示例：

青蛙的约会

两只青蛙在网上相识了，它们聊得很开心，于是觉得很有必要见一面。它们很高兴地发现它们住在同一条纬度线上，于是它们约定各自朝西跳，直到碰面为止。可是它们出发之前忘记了一件很重要的事情，既没有问清楚对方的特征，也没有约定见面的具体位置。不过青蛙们都是很乐观的，它们觉得只要一直朝着某个方向跳下去，总能碰到对方的。但是除非这两只青蛙在同一时间跳到同一点上，不然是永远都不可能碰面的。为了帮助这两只乐观的青蛙，你被要求写一个程序来判断这两只青蛙是否能够碰面，会在什么时候碰面。

我们把这两只青蛙分别叫做青蛙A和青蛙B，并且规定纬度线上东经0度处为原点，由东往西为正方向，单位长度1米，这样我们就得到了一条首尾相接的数轴。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。

输入 输入只包括一行5个整数x，y，m，n，L，

其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。

输出 输出碰面所需要的跳跃次数，如果永远不可能碰面则输出一行"Impossible"

输入示例

代码语言：javascript复制
1 2 3 4 5

输出示例

代码语言：javascript复制
4

题目分析

设跳次数为t，则跳t次后两个青蛙的位置分别为(x mt) mod L、(y nt) mod L，相遇即是(x mt)%L=(y nt)%L转化为ax by=c方程： (m-n)t kL=y-x。设a=m-n，b=L，c=y-x，然后套用拓展欧几里得即可得出答案。

代码语言：javascript复制
package action;

import java.util.Scanner;

// 求解同余方程的本质就是求线性方程
// 将求余方程转化为线性方程
public class demo2 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		long x = sc.nextInt(); // 坐标
		long y = sc.nextInt(); // 坐标
		long m = sc.nextInt(); // A第一次跳
		long n = sc.nextInt(); // B第一次跳
		long l = sc.nextInt(); // 维度总长
		sc.close();
		long a = m - n;
		long b = l;
		m = y - x;
		long d = 0;
		try {
			d = ExtGcd.linearEquation(a, b, m);
		} catch (Exception e) {
			System.out.println("Impossible");
		} // 求解线性方程
		long x0 = ExtGcd.x;
		b /= d; // 约一下
		b = Math.abs(b); // 有可能小于0
		/* =========这里是AC的关键=========== */
		x0 = (x0 % b   b) % b; // 要求大于0的第一个解
		System.out.println(x0);
	}

	// 私有的静态的内部类
	private static class ExtGcd {
		static long x, y;

		public static long ext_gcd(long a, long b) {
			if (b == 0) {
				x = 1;
				y = 0;
				return a;
			}
			long res = ext_gcd(b, a % b);
			long x1 = x;
			x = y;
			y = x1 - a / b * y;
			return res;
		}

		public static long linearEquation(long a, long b, long m) throws Exception {
			long d = ext_gcd(a, b);
			if (m % d != 0)
				throw new Exception("无解");
			long n = m / d;
			x *= n;
			y *= n;
			return d;
		}
	}
}
海外加速

0 人点赞