數論筆記

来源:https://www.cnblogs.com/wanguan/archive/2022/10/02/16747794.html
-Advertisement-
Play Games

♠ use C++11 倍數 若 $a,b,k \in \mathbb N$,且 $a \times k=b$,那麼 $b$ 是 $a$ 的倍數,稱 $a$ 整除 $b$,記作 $a \mid b$。 $[1,n]\in \mathbb N$ 中 $x \in \mathbb N$ 的倍數有 $\l ...


use C++11

倍數

  1. \(a,b,k \in \mathbb N\),且 \(a \times k=b\),那麼 \(b\)\(a\) 的倍數,稱 \(a\) 整除 \(b\),記作 \(a \mid b\)

  2. \([1,n]\in \mathbb N\)\(x \in \mathbb N\) 的倍數有 \(\left \lfloor \dfrac{n}{x} \right \rfloor\) 個。

約數

  1. \(a \mid b\)\(a,b\in\mathbb N\),那麼 \(a\)\(b\) 的約數。

  2. \(a \in \mathbb N\) 的約數個數是有限的,記作 \(\operatorname d(n)\)\(\in \mathbb Z\)

  3. 快速算一個序列的 \(\operatorname d(n)\):設一個計數數組對應每個數,初始為 0,從左到右計算每個數,對於每個倍數加 1,當整個序列計算完後,計數數組的值是其對應數字的約數個數,時間複雜度 \(\mathcal{O}(n\operatorname{log}n)\)。下麵是一個例子:

n    1  2  3  4  5  6
d(n) 0  0  0  0  0  0  start
    +1 +1 +1 +1 +1 +1  step 1 in number 1
     0 +1  0 +1  0 +1  step 2 in number 2
     0  0 +1  0  0 +1  step 3 in number 3
     .....and more
     1  2  2  3  2  4  end

素數

  1. 1 不是素數也不是合數。

  2. 下麵是一串判斷 \(n\in \mathbb N\) 是否是素數的代碼,時間複雜度 \(\mathcal{O}(\sqrt n)\)

bool is_prime(long long n){
	if(n==1)	return false;
	for(long long i=1;i<=n/i;++i){
		if(x%i==0)	return false;
	}
	return true;
}
  1. 計算一個序列每個數是否是素數:朴素篩法,有較多重覆判斷,時間複雜度 \(\mathcal{O}(n\operatorname{log}n)\);埃式篩法,僅是素數才向後篩,優化朴素篩法,時間複雜度 \(\mathcal{O}(n\operatorname{log log}n)\),接近線性篩。

最大公約數

  1. \(a,b\in \mathbb N\)\(k \mid a,b \in \mathbb N\),且不存在更大的 \(k\),稱 \(k\)\(a,b\) 的最大公約數。

  2. 快速求 \(a,b\in \mathbb N\) 的最大公約數,歐幾裡得定理:\(\gcd(a,b)=\gcd(b,a \bmod b)\)

  3. 已知 \(a,b \in \mathbb N\),可找到 \(x,y \in \mathbb Z\) 使 \(ax +by=\gcd(a,b)\),若 \(ax+by=1\) 有解,則 \(a\)\(b\) 互質。

  4. 擴展歐幾裡得,一定存在 \(x,y\in \mathbb N\) 使貝祖等式 \(ax +by=\gcd(a,b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times b + a \bmod b) x + by = \gcd(b,a\bmod b)\)\(\Rightarrow (\left \lfloor a \div b \right \rfloor \times x + y) b +(a \bmod b)x\),可得新的方程 \(b \times x'+(a \bmod b)\times y' = \gcd(b,a\bmod b)\) 因此可得 \(\begin{cases}x'=(\left \lfloor a \div b \right \rfloor\times x+y)\\y'=x\end{cases}\),同樣倒推可得特解 \(\begin{cases}x=y'\\y=x'-(\left \lfloor a \div b \right \rfloor\times y')\end{cases}\),下麵是遞歸代碼實現:

array<int,3> exgcd(int a,int b){
	if(b==0){
		return {1,0,a};
		//當b=0時,等式為ax=gcd(a,0),即ax=a
		//得x=1,y=0
	}
	array<int,3> ans=exgcd(b,a%b);
	int temp=ans[0];
	ans[0]=ans[1];
	ans[1]=temp-a/b*ans[1];
	return ans;//ans[0]為x,ans[1]為y,ans[2]為gcd(a,b)
}
  1. 當求得貝祖等式特解 \(x_0,y_0\in \mathbb N\) 後,可得 \(x,y\in \mathbb N\) 通解,設 \(g=\gcd(a,b)\) 通解為 \(\begin{cases}x=x_0+t\times b\div g\\y = y_0- t \times a \div g\end{cases}\),推導過程:\(\begin{cases}ax+by=g\\ax_0+bx_0=g\end{cases}\)\(\Rightarrow (x-x_0)a+(y-y_0)b=0\)\(\Rightarrow (x-x_0)a=(y_0-y)b\)\(\Rightarrow (x-x_0)\dfrac{a}{g}=(y_0-y)\dfrac{b}{g}\)\(\Rightarrow \begin{cases}x-x_0=t\times \dfrac{b}{g}\\y_0-y=t \times \dfrac{a}{g}\end{cases}\)\(\Rightarrow \begin{cases} x=x_0+t\times\dfrac{b}{g}\\y=y_0-t\times\dfrac{a}{g}\end{cases}\),其中 \(x\) 的第一個解是 \(\bigg(x\bmod\dfrac{b}{g}+\dfrac{b}{g}\bigg)\bmod \dfrac{b}{g}\)

模運算

  1. 已知 \(a,b,p\in \mathbb N\)\((a+b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)\((a-b)\bmod p=(a\bmod p+b\bmod p)\bmod p\)\((a\times b)\bmod p=(a \bmod p\times b\bmod p)\bmod p\)

  2. 若需要進行除法的模運算,與普通的不同,例子:\(\dfrac{20}{10}\bmod 5=2\)\(\nRightarrow\dfrac{20 \bmod 10}{10\bmod 10}\bmod 5=0\),所以為了求 \((a\div b) \bmod p\)\(a,b,p\in\mathbb N\),需要找到 \(b\) 的乘法逆元 \(x\in\mathbb N\),將算式變成 \((a\times x)\bmod p\)

  3. 已知 \(a,x,m\in \mathbb N\)\(ax \equiv 1\pmod p\)\(\Rightarrow ax \bmod p=1\)\(\Rightarrow ax-\left\lfloor\dfrac{ax}{p}\right\rfloor\times p=1\),稱 \(x\) 是關於 \(a\) 的乘法逆元,將 \(-\left\lfloor\dfrac{ax}{p}\right\rfloor\)\(y\) 替代,得 \(ax+py=1\),即找到 \(x\) 的值即可找到 \(a\) 的乘法逆元,也可知 \(a,p\) 必須要互質。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 我們在創建條形碼時,如果以圖片的方式將創建好的條碼保存到指定文件夾路徑,可以在程式中直接載入圖片使用;已生成的條碼圖片,需要通過讀取圖片中的條碼信息,如條碼類型、條碼繪製區域在圖片中的四個頂點坐標位置等,可參考本文中的方法。 註:讀取時,也支持讀取二維碼類型。 引入dll 調用API:Spire.B ...
  • 大家好,我是痞子衡,是正經搞技術的痞子。今天痞子衡給大家介紹的是i.MXRT10xx系列MCU外接24MHz晶振的作用。 痞子衡之前寫過一篇關於時鐘引腳的文章 《i.MXRT1xxx系列MCU時鐘相關功能引腳的作用》,裡面簡單提及了外部晶振相關引腳的作用,但是並沒有詳細展開。最近在客戶支持中,有客戶 ...
  • MySQL基礎知識02 4.CRUD 資料庫CRUD語句:增(create)、刪(delete)、改(update)、查(Retrieve) Insert 語句 (添加數據) Update 語句(更新數據) Delete 語句(刪除數據) Select 語句 (查找數據) 指對資料庫中表記錄的操作( ...
  • MySQL基本知識 1.資料庫 1.1.創建資料庫 語法: CREATE DATABASE [IF NOT EXISTS] db_name [create_specification[,create_specification]...] create_specification: [DEFAULT] ...
  • 一、在Bootstra5中使用媒體對象 Bootstrap 媒體對象在版本 5 中已經停止支持了。但是,我們仍然可以使用 flex 和 margin 創建包含左對齊或右對齊媒體對象(如圖像或視頻)以及文本內容(如博客評論、推文等)的佈局 。 <!doctype html> <html lang="z ...
  • 一、節流 概念:在規定的間隔時間範圍內不會重覆觸發回調,只有大於這個時間間隔才會觸發回調,把頻繁觸發變為少量觸發。 類似於技能CD。 應用:點擊按鈕,輪播圖點擊左右箭頭。 插件lodash.js,它裡面封裝了函數的防抖與節流業務。 <p>計數器:<span>0</span></p> <button> ...
  • Spring 5框架 一、Spring概念 1、Spring是輕量級的JavaEE框架 2、Spring可以解決企業應用開發的複雜性 3、Spring有兩個核心部分:IOC和AOP ​ 1)IOC:控制反轉,把創建對象過程交給Spring進行管理 ​ 2)AOP:面向切麵,不修改源代碼進行功能增強 ...
  • LinkList可以定義指向List的指針 1.當函數參數為LinkList L時,意味著只改變或操作List的內容,而不需要改變L這個指針 如 Status GetElem(LinkList L,int i,ElemType) 2.當參數為LinkList &L時,意味著需要改變或操作L這個指針本 ...
一周排行
    -Advertisement-
    Play Games
  • public static void GetRegistData() { string name = "huishuangzhu"; //搜索到註冊表根目錄 RegistryKey hkml = Registry.ClassesRoot; //搜索到註冊表根目錄下的XXX文件夾。 RegistryK ...
  • 用acme.sh自動部署功能變數名稱證書 安裝ACME 目前使用量最大的免費SSL證書就是Let’s Encrypt,自2018-03開始,Let’s Encrypt官方發佈上線了免費的SSL泛功能變數名稱證書,目前通過DNS方式獲取比較快,國內可以通過鵝雲的DNSPod功能變數名稱API或者貓雲功能變數名稱API自動簽發Let’ ...
  • 經常看到有群友調侃“為什麼搞Java的總在學習JVM調優?那是因為Java爛!我們.NET就不需要搞這些!”真的是這樣嗎?今天我就用一個案例來分析一下。 昨天,一位學生問了我一個問題:他建了一個預設的ASP.NET Core Web API的項目,也就是那個WeatherForecast的預設項目模 ...
  • 1、環境搭建 1.1 依賴 <!-- nacos註冊中心 註解 @EnableDiscoveryClient --> <dependency> <groupId>com.alibaba.cloud</groupId> <artifactId>spring-cloud-starter-alibaba- ...
  • ULID:Universally Unique Lexicographically Sortable Identifier(通用唯一詞典分類標識符) UUID:Universally Unique Identifier(通用唯一標識符) 為什麼不選擇UUID UUID 目前有 5 個版本: 版本1: ...
  • 虛基類/抽象類 抽象類:有純虛函數的類 虛繼承 通過修飾繼承方式, 如代碼2是虛繼承,被虛繼承的類稱為虛基類 虛繼承派生類的記憶體佈局方式 先是vbptr => 派生類的數據 =>基類的數據 , 對比代碼1和代碼2,發現原本基類數據在前面,派生類數據在後面,但是在虛繼承的時候 基類數據方式放到了後面, ...
  • 下麵給出 Kafka 一些重要概念,讓大家對 Kafka 有個整體的認識和感知,後面還會詳細的解析每一個概念的作用以及更深入的原理 • Producer:消息生產者,向 Kafka Broker 發消息的客戶端。 • Consumer:消息消費者,從 Kafka Broker 取消息的客戶端。 • ...
  • 前面介紹了對稱加密演算法,本文將介紹密碼學中另一類重要應用:消息摘要(Digest),什麼是消息摘要?簡單的定義是:對一份數據,進行一個單向的Hash函數,生成一個固定長度的Hash值,這個值就是這份數據的摘要,也稱為指紋。 ...
  • 弟弟最近要考試,臨時抱佛腳在網上找了一堆學習資料複習,這不剛就來找我了,說PDF上有水印,影響閱讀效果,到時候考不好就怪資料不行,氣的我差點當場想把他揍一頓! 算了,弟弟長大了,看在打不過他的份上,就不打他了~ 稍加思索,我想起了Python不是可以去水印?說搞就搞! 去除水印原理 去除方法: 用 ...
  • 作者:陳昌浩 1 導讀 if…else…在代碼中經常使用,聽說可以通過Java 8的Function介面來消滅if…else…!Function介面是什麼?如果通過Function介面介面消滅if…else…呢?讓我們一起來探索一下吧。 2 Function介面 Function介面就是一個有且僅有 ...