【蓝桥杯省赛】冲刺练习题【数学公式】倒计时【06】天(准考证组委会已下发，请查询)
??🙏🤗距離【第十三屆藍橋杯4月9日省賽】僅剩【06天】🤗🙏
📋今日題型：【數(shù)學公式】📋
??🤗循環(huán)是一切暴力的基礎，暴力基礎，轉起來。🤗??
🤗國一鎮(zhèn)樓🤗
📋比賽題目與分數(shù)比例📋
確認范圍：
結果填空題5道，共計45分。
程序設計題5道，共計105分。
??🤗刷題安排🤗??
| 日期 | 題目類型 | 題目數(shù)量 |
| 3月25日 | 循環(huán) | 6 |
| 3月26日 | 超大數(shù) | 6 |
| 3月27日 | 數(shù)組 | 6 |
| 3月28日 | 枚舉 | 6 |
| 3月29日 | 遞歸 | 6 |
| 3月30日 | 繪圖 | 6 |
| 3月31日 | 深搜廣搜 | 5 |
| 4月1日 | 動態(tài)規(guī)劃 | 5 |
| 4月2日 | 填空題 | 5 |
| 4月3日 | 數(shù)學公式:查詢準考證 點擊查詢準考證鏈接 | 5 |
| 4月4日 | 第十屆省賽題 | 10 |
| 4月5日 | 第十一屆省賽題 | 10 |
| 4月6日 | 第十二屆省賽1套題 | 10 |
| 4月7日 | 第十二屆省賽2套題 | 10 |
| 4月8日 | 經(jīng)典題目練習 | 8 |
| 4月9日 | 9點考試 |
目錄
1、判斷質數(shù)
2、分解質因數(shù)
3、快速冪
3、歐幾里得定力
4、海倫公式（求三角形面積）
5、排列數(shù)公式
排列數(shù):
排列數(shù)公式
符號
推導過程
示例：
附加1：矩陣相乘
附加2：線性同余方程(B組以上)
理論示例：
代碼示例：
青蛙的約會
1、判斷質數(shù)
質數(shù)又稱為素數(shù)，是指大于1的并且除了1和它本身外，沒有其他因數(shù)的自然數(shù)。
判斷一個數(shù)是否是質數(shù)
假設該數(shù)為n， 我們只需要判斷內是否有n的因子。如果有，則n為合數(shù)，否則，n為質數(shù)。
這種方法被稱為試除法， 即試著除一下所有可能的因子。
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、分解質因數(shù)
根據(jù)算術基本定理又稱唯一分解定理，對于任何一個合數(shù)， 我們都可以用幾個質數(shù)的冪的乘積來表示。
?
接下來我們利用這個公式分解質因數(shù)。
設一個質數(shù)為p.如果n%p == 0，那么p就是n的一個質因數(shù)，接下來就是求p的指數(shù)，我們讓n = n/p, 這樣就從n中剔除了一個p,接著重復上述兩步，直到n%p ！= 0
?
3、快速冪
當我們計算時，常用的做法是對n連乘k次， 但如果k特別大，假如k = 1e6， 如果仍然對n連乘1e6次的話，時間消耗就太大了。那么我們如何在短時間內求出一個數(shù)的k次方呢。
求
?
快速冪
?
沒有處理超大數(shù)
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^bint res = 1; // res保存結果while (b != 0) {if ((b & 1) == 1) { // 如果k的二進制數(shù)的最后一位是 1。 比如1011 & 1 = 1res = (res * a);}a = a * a;// 得到 a^1, a^2, a^4, a^8, .....b = b >> 1; // 將b右移一位，去掉最低位。為了開始判斷下一位。}return res;}}3、歐幾里得定力
最大公約數(shù)、最小公倍數(shù)
package Action;public class demo {/** 求最大公約數(shù) 最小公倍數(shù) 思路：根據(jù)歐幾里得定理 gcd(a,b)=gcd(b,a%b);*/static int gcd(int a, int b) {// 出口：b=0;5和0的最大公約數(shù)是5if (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、排列數(shù)公式
排列數(shù)公式就是從n個不同元素中，任取m（m≤n）個元素（被取出的元素各不相同），按照一定的順序排成一列，叫做從n個不同元素中取出m個元素的一個排列。排列與元素的順序有關，組合與順序無關。加法原理和乘法原理是排列和組合的基礎。
排列數(shù):
從n個不同的元素中任取m(m≤n)個元素的所有排列的個數(shù)，叫做從n個不同的元素中取出m(m≤n)個元素的排列數(shù)。記作符號?。A是英文arrangement（排列）的第一個大寫字母。
例如，從7個不同的元素中任取5個元素的排列數(shù)為?，從10個不同的元素中任取7個元素的排列數(shù)為。
排列數(shù)公式
?公式A是排列公式，從N個元素取M個進行排列（即排序）。
符號
C：組合數(shù)
A：排列數(shù)（在舊教材為P）
N：元素的總個數(shù)
M：參與選擇的元素個數(shù)
!：階乘，如5！=5×4×3×2×1=120
C：Combination 組合
P：Permutation排列 (現(xiàn)在教材為A-Arrangement)
推導過程
求排列數(shù)可以按依次填m個空位來考慮：假定有排好順序的m個空位,從n個不同元素a1,a2,a3,…,an中任意取m個去填空,一個空位填1個元素，每一種填法就對應1個排列，因此，所有不同填法的種數(shù)就是排列數(shù)。
填空可分為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種填法。
根據(jù)分步計數(shù)原理，全部填滿m個空位共有n(n-1)(n-2)…(n-m+1)種填法。所以得到公式：
?這里n，m∈N*，并且m≤n這個公式叫做排列數(shù)公式其中，公式右邊第一個因數(shù)是n，后面的每個因數(shù)都比它前面一個因數(shù)少1，最后個因數(shù)為n-m+1，共有m個因數(shù)相乘。
排列數(shù)公式還可以寫成：
注意：為了保證公式在n=m時成立，特規(guī)定0! =1。
示例：
在10個球中，任意取3個（不放回），求有多少種取法？
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
問題描述
小明最近在為線性代數(shù)而頭疼，線性代數(shù)確實很抽象（也很無聊），可惜他的老師正在講這矩陣乘法這一段內容。
當然，小明上課打瞌睡也沒問題，但線性代數(shù)的習題可是很可怕的。
小明希望你來幫他完成這個任務。
現(xiàn)在給你一個ai行aj列的矩陣和一個bi行bj列的矩陣，
要你求出他們相乘的積（當然也是矩陣）。
(輸入數(shù)據(jù)保證aj=bi,不需要判斷)
輸入格式
輸入文件共有ai+bi+2行，并且輸入的所有數(shù)為整數(shù)（long long范圍內）。
第1行：ai 和 aj
第2~ai+2行：矩陣a的所有元素
第ai+3行：bi 和 bj
第ai+3~ai+bi+3行：矩陣b的所有元素
輸出格式
輸出矩陣a和矩陣b的積（矩陣c)
（ai行bj列）
樣例輸入
2 2 12 23 45 56 2 2 78 89 45 56樣例輸出
1971 2356 6030 7141 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組以上)
數(shù)論中，線性同余方程是最基本的同余方程，“線性”表示方程的未知數(shù)次數(shù)是一次.
在數(shù)論中，線性同余方程是最基本的同余方程，“線性”表示方程的未知數(shù)次數(shù)是一次，即形如：
ax≡b (mod n)的方程。
此方程有解當且僅當 b 能夠被 a 與 n 的最大公約數(shù)整除（記作 gcd(a,n) | b）。
這時，如果 x0 是方程的一個解，那么所有的解可以表示為：
{x0+kn/d|(k∈z)}其中 d 是a 與 n 的最大公約數(shù)。在模 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。
代碼示例：
青蛙的約會
兩只青蛙在網(wǎng)上相識了，它們聊得很開心，于是覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。可是它們出發(fā)之前忘記了一件很重要的事情，既沒有問清楚對方的特征，也沒有約定見面的具體位置。不過青蛙們都是很樂觀的，它們覺得只要一直朝著某個方向跳下去，總能碰到對方的。但是除非這兩只青蛙在同一時間跳到同一點上，不然是永遠都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個程序來判斷這兩只青蛙是否能夠碰面，會在什么時候碰面。
我們把這兩只青蛙分別叫做青蛙A和青蛙B，并且規(guī)定緯度線上東經(jīng)0度處為原點，由東往西為正方向，單位長度1米，這樣我們就得到了一條首尾相接的數(shù)軸。設青蛙A的出發(fā)點坐標是x，青蛙B的出發(fā)點坐標是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩只青蛙跳一次所花費的時間相同。緯度線總長L米。現(xiàn)在要你求出它們跳了幾次以后才會碰面。
輸入
輸入只包括一行5個整數(shù)x，y，m，n，L，
其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。
輸出
輸出碰面所需要的跳躍次數(shù)，如果永遠不可能碰面則輸出一行"Impossible"
輸入示例
1 2 3 4 5輸出示例
4題目分析
設跳次數(shù)為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，然后套用拓展歐幾里得即可得出答案。
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);}// 私有的靜態(tài)的內部類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;}} } 與50位技術專家面對面20年技術見證，附贈技術全景圖總結
以上是生活随笔為你收集整理的【蓝桥杯省赛】冲刺练习题【数学公式】倒计时【06】天(准考证组委会已下发，请查询)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Python基础——PyCharm版本—
- 下一篇： Python基础——PyCharm版本—