【聲明：本文為原創(chuàng)文章,未經(jīng)同意,嚴禁轉(zhuǎn)載和抄襲,違者將追究其法律責任】

/?寫在前面的話?/

蘇世機試小課堂，考研機試不再慌！

公主號：蘇世學社考研? 蘇世計算機考研

數(shù)論一度被認為是漂亮的但沒什么大用處的純數(shù)學學科。今天，有關數(shù)論的算法被廣泛使用，部分是因為基于大素數(shù)的密碼系統(tǒng)的發(fā)明。這些系統(tǒng)的可行性在于我們?nèi)菀浊蟪龃笏財?shù)，而系統(tǒng)的安全性在于大素數(shù)的積難以分解。本文介紹一些初等數(shù)論和相關算法，它們是一些應用的基礎。

數(shù)論常用內(nèi)容介紹

1

同模余定理

1.1 概念

同余，顧名思義，就是許多數(shù)被一個數(shù)d除，有相同的余數(shù)。d在數(shù)學上的稱謂為模。比如a=7,b=2,d=5，那么我們說a和b是模d同余的，因為他們都有相同的余數(shù)1。

可以看出，當x<d的時候，所有的x都對d同商，對于同余有三種說法是等價的，分別是：

①a和b是模d同余的；

②存在某個整數(shù)n,使得a = b + nd；

③d整除(a - b)。

?

1.2 常用操作

(a+b)%d=(a%d+b%d)%d；

(a-b)%d=(a%d-b%d)%d；

(a*b)%d=(a%d*b%d)%d。

?

1.3 棧的應用——括號匹配

題目描述

S(n)=n^5，求S(n)除以3的余數(shù)。

輸入描述

每行輸入一個整數(shù)n(0 < n < 1000000)，處理到文件結(jié)束。

輸出描述

輸出S(n)%3的結(jié)果并換行。

樣例輸入

? ? 1

? ? 2

樣例輸出

? ? 1

? ? 2

思路分析

n^5超過了long long的范圍，題目要求對結(jié)果%3，可運用同余模定理。

S(n)%3=(n*n*n*n*n)%3=((n%3)*(n%3)*(n%3)*(n%3)*(n%3))%3

代碼實現(xiàn)

運行結(jié)果

2

最大公約數(shù)（GCD）

2.1?概念

最大公約數(shù)，也稱最大公約數(shù)、最大公因子，指兩個或多個整數(shù)共有約數(shù)最大的一個。a,b的最大公約數(shù)記為(a,b)，a,b,c的最大公約數(shù)記為(a,b,c)，多個整數(shù)的最大公約數(shù)也是類似的記號。

2.2 解題方法

（1）窮舉法一：

用一個臨時變量t保存其中一個數(shù)，然后看兩個數(shù)是否都能被t整除，能就輸出，不能就減1，直到減到1，1是任意兩個正整數(shù)的公約數(shù)。

（2）窮舉法二：

求出兩個數(shù)的所有公因子，累乘得到最大公約數(shù)。

（3）輾轉(zhuǎn)相除法：

兩個數(shù)輾轉(zhuǎn)相除直到余數(shù)為0。

（4）輾轉(zhuǎn)相減法：

3

最小公倍數(shù)

3.1?概念

兩個或多個整數(shù)公有的倍數(shù)叫做它們的公倍數(shù)，除了0以外最小的一個公倍數(shù)叫做這幾個整數(shù)的最小公倍數(shù)。整數(shù)a,b的最小公倍數(shù)記為[a,b]，整數(shù)a,b,c的最小公倍數(shù)記為[a,b,c]，多個整數(shù)的最小公倍數(shù)是同樣的記號。

?

3.2?代碼思路和實現(xiàn)

①設置一個臨時變量t初始值等于其中一個數(shù)，開始遍歷到兩個數(shù)的乘積為止，遇到一個數(shù)能同時被a,b整除就跳出循環(huán)打印輸出。

這里當a和b的乘積太大溢出了怎么辦呢？

②利用一個公式：兩個數(shù)的乘積等于它們的最大公約數(shù)乘最小公倍數(shù)。所以求最小公倍數(shù)就用兩數(shù)乘積除以它們的最大公約數(shù)。

這里以輾轉(zhuǎn)相減法求最大公約數(shù)為例：

4

素數(shù)判定

4.1 概念

素數(shù)，又叫質(zhì)數(shù)，有無限多個。定義為在大于1的自然數(shù)中，除了1和它本身外不再有其他因數(shù)，這樣的數(shù)叫做質(zhì)數(shù)。

比如13就是素數(shù)，它不能被2~12的任意一個整數(shù)整除。

?

4.2 判斷方法及代碼實現(xiàn)

簡單粗暴的方法就是遍歷從2到這個數(shù)n-1，時間復雜度為O(n)，想想還有沒有可以減少遍歷次數(shù)的上限值呢？

如果一個數(shù)能被2整除，還需要試4,6,8....嗎？

如果一個數(shù)能被3整除，還需要試9,15,21....嗎？

所以，一個數(shù)如果有因子那么在它的平方根數(shù)以內(nèi)就應該有，否則就沒有。

參考代碼如下：

5

素數(shù)篩選

5.1?概念

有時候我們可能會遇到打印一個整數(shù)以內(nèi)的所有素數(shù)或者求所有素數(shù)個數(shù)的問題，這個時候我們再一個一個去判斷是不是素數(shù)時間成本就太高了，所以我們需要提前打表篩選。

?

5.2?典型題目及代碼思路和實現(xiàn)

給定一個數(shù)字n，求出小于等于n的素數(shù)的個數(shù)，假設n<=1e6。

（1）埃氏篩選法

遍歷2~N的所有數(shù)，如果是素數(shù)，就把它的倍數(shù)全部標記為合數(shù)，最后根據(jù)題目條件輸出即可。

（2）歐拉篩選法

原理是保證2~N內(nèi)的每一個合數(shù)都能被唯一分解成它的最小質(zhì)因數(shù)與除自己外最大的因數(shù)相乘的形式。

假設所有1e6范圍內(nèi)的數(shù)都是素數(shù)，枚舉2~N中的每一個數(shù)作為篩法中的“除自己外的最大因數(shù)”，如果沒有被標記為合數(shù)，就放進素數(shù)表，再將這個最大因數(shù)與素數(shù)表中已經(jīng)找到的素數(shù)作為最小質(zhì)因數(shù)相乘，將得到的數(shù)標記為合數(shù)，最后根據(jù)題目條件相應輸出即可。

6

分解素因數(shù)

6.1?概念

每個合數(shù)都可以寫成幾個質(zhì)數(shù)相乘的形式。其中每個質(zhì)數(shù)都是這個合數(shù)的因數(shù)，叫做這個合數(shù)的分解質(zhì)因數(shù)。分解質(zhì)因數(shù)只針對合數(shù)。分解質(zhì)因數(shù)的算式叫短除法，求一個數(shù)分解質(zhì)因數(shù)，要從最小的質(zhì)數(shù)除起，一直除到結(jié)果為質(zhì)數(shù)為止。

?

6.2?代碼實現(xiàn)

7

二分快速冪

求a的b次方，自定義pow庫函數(shù)：

pow(a,b)是數(shù)學頭文件cmath里面有的函數(shù)，但是返回值是double，數(shù)據(jù)有精度誤差。

但是當數(shù)據(jù)量大時會超時，使用自定義的pow也要超時，這時必須二分快速冪。

（1）遞歸寫法：

（2）循環(huán)寫法：

蘇世學社旗下品牌，專注于計算機考研

計算機考研一手資訊，原創(chuàng)高質(zhì)量干貨

深度的學習分享丨咨詢前輩丨個性化指導