數論筆記

来源: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
  • 簡介 本文的初衷是希望幫助那些有其它平臺視覺演算法開發經驗的人能快速轉入Halcon平臺下,通過文中的示例開發者能快速瞭解一個Halcon項目開發的基本步驟,讓開發者能把精力完全集中到演算法的開發上面。 首先,你需要安裝Halcon,HALCON 18.11.0.1的安裝包會放在文章末尾。安裝包分開發和 ...
  • 本文是對Datawhale的動手學數據分析課程的學習總結,記錄了整體的學習過程、答案以及個人感想,代碼較為詳細。 ...
  • JZ7重建二叉樹 描述 給定節點數為 n 的二叉樹的前序遍歷和中序遍歷結果,請重建出該二叉樹並返回它的頭結點。 例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6} 提示: 1.vin.length == pre.length 2.pre 和 vin ...
  • 我們都知道在Java編程中多線程的同步使用synchronized關鍵字來標識,那麼這個關鍵字在JVM底層到底是如何實現的呢。 我們先來思考一下如果我們自己實現的一個鎖該怎麼做呢: 首先肯定要有個標記記錄對象是否已經上鎖,執行同步代碼之前判斷這個標誌,如果對象已經上鎖線程就阻塞等待鎖的釋放。 其次要 ...
  • 目錄 一.OpenGL 色階 1.Windows OpenGL ES 版本 2.Windows OpenGL 版本 二.OpenGL 色階 GLSL Shader 三.猜你喜歡 零基礎 OpenGL ES 學習路線推薦 : OpenGL ES 學習目錄 >> OpenGL ES 基礎 零基礎 Ope ...
  • 1. 查看Linux伺服器版本信息 # cat /etc/redhat-release CentOS Linux release 7.4.1708 (Core) 2. 禪道開源版安裝包下載 wget http://dl.cnezsoft.com/zentao/9.8.2/ZenTaoPMS.9.8. ...
  • Spring 框架可以為 Java 應用程式開發提供全面的基礎設施支持,它是現在非常流行的 Java 開源框架,對於一個 Java 開發人員來說,熟練掌握 Spring 是必不可少的。 ...
  • 前言 本篇是c++總結的第二篇,關於c++的對象模型,在構造、拷貝虛函數上重點分析,也包含了c++11class的新用法和特性,如有不當,還請指教! c++三大特性 訪問許可權 ​ 在c++中通過public、protected、private三個關鍵字來控製成員變數和成員函數的訪問許可權,它們分別表示 ...
  • 一.小結 1.使用二維數組來存儲表格 2.可以使用以下語法來聲明二維數組變數: 元素類型[ ] [ ]數組變數 3.可以使用以下語法來創建二維數組變數: new 元素類型 [行的個數][列的個數] 4.使用下麵的語法表示二維數組中的每個元素: 數組變數[行下標][列的個數] 5.可使用數組初始化語法 ...
  • typimg是一款為typora編輯器提供圖像自定義上傳服務的工具,該工具將在typora中輸入的網路圖片、本地圖片、剪貼板圖片/截圖上傳到博客園,支持在MacOS、Windiws、Linux三個平臺上運行。 ...