Ofnoname

摘要： 歐拉函數(shù)（Euler's totient function），記作 \(\phi(n)\)，是數(shù)論中一個非常重要的函數(shù)。它的定義很簡單： 對于正整數(shù) \(n\)，\(\phi(n)\) 表示小于等于 \(n\) 且與 \(n\) 互質(zhì)的正整數(shù)的個數(shù)。 \(\phi(1) = 1\)（只有 1 與 1 閱讀全文

摘要： 在數(shù)論和密碼學(xué)中，歐幾里得算法（Euclidean Algorithm）是一個古老而重要的算法，用于計算兩個整數(shù)的最大公約數(shù)（GCD）。 歐幾里得算法（更相減損法） 歐幾里得算法基于以下原理：兩個整數(shù)的最大公約數(shù)等于其中較小的數(shù)和兩數(shù)相除余數(shù)的最大公約數(shù)。用數(shù)學(xué)公式表示為： \[\gcd(a, b) 閱讀全文

摘要： 快速冪 快速冪（Fast Exponentiation）算法解決這樣一個問題：求解自然數(shù)的指數(shù)運算。計算 \(a^b\) 時，按照指數(shù)定義的樸素的方法是通過連續(xù)相乘： \[a^b = \underbrace{a \times a \times \cdots \times a}_{b\text{次}} 閱讀全文

摘要： Nautilus 是 Ubuntu 默認的文件管理器。默認情況下，系統(tǒng)會在側(cè)邊欄顯示"圖片"、"視頻"、"文檔"等用戶目錄文件夾，但這些可能并不是我們經(jīng)常訪問的位置。 （默認情況下，紅框處還存在音樂，圖片等一串文件夾） 常見的困擾包括： 希望隱藏不常用的默認文件夾 想要將側(cè)邊欄目錄指向其他分區(qū)或外部 閱讀全文

摘要： 從“分治”到“點分治” 在算法世界里，“分治”幾乎是最經(jīng)典的套路：把一個大問題拆成若干規(guī)模較小的子問題，遞歸解決，再把答案拼接。歸并排序、快速冪，都是這樣耳熟能詳?shù)睦印?數(shù)組有天然的“中點”，可以左右對半分；而無根樹由節(jié)點與邊連接，我們也可以選擇一個節(jié)點，將樹分為多個部分分治，這就叫做“點分治”。 閱讀全文

摘要： 上期回顧：http://www.rzrgm.cn/ofnoname/p/18994725，http://www.rzrgm.cn/ofnoname/p/19034861 我們學(xué)習(xí)了如何把一維數(shù)組“分塊”，在每塊里維護額外信息，從而在查詢與修改之間取得平衡。通過解決區(qū)間眾數(shù)問題，我們還 閱讀全文

摘要： 上期回顧：http://www.rzrgm.cn/ofnoname/p/18994725 在上一篇文章中，我們介紹了塊狀數(shù)組的基本原理。 而區(qū)間眾數(shù)問題就是一個典型的適合用分塊解決的問題。由于眾數(shù)不滿足區(qū)間可加性，直接使用傳統(tǒng)數(shù)據(jù)結(jié)構(gòu)（如線段樹）較為困難。但塊狀數(shù)組通過預(yù)處理塊內(nèi)信息，結(jié)合零 閱讀全文

摘要： 在數(shù)學(xué)和計算機計算實戰(zhàn)中，我們現(xiàn)在要判斷一個整數(shù) \(n\) 是否可以表示為任意某個正整數(shù) \(a\) 的冪，即判斷是否存在整數(shù) \(a\) 和 \(b\) 使得 \(n = a^b\) 最暴力的方案是通過遍歷： 遍歷 \(a\)：嘗試所有可能的 \(a\)，范圍從 \(2\) 到 \(\sqrt{ 閱讀全文

摘要： 生活中處處可見分塊思想的影子。走進圖書館，書籍按照學(xué)科分類，讀者只需先定位大類別，再在小范圍內(nèi)查找，就能快速找到目標書籍；小區(qū)的快遞柜更是將大量包裹按照格口大小和編號分塊存放，快遞員按區(qū)域投放，收件人按編號取件，極大提升了物流效率。這種 “先整體劃分，再局部處理” 的思路，在算法世界中演變成了一種高 閱讀全文

摘要： 有模數(shù)的乘法逆元是數(shù)論計算中的一個基本概念。在日常生活與科學(xué)計算中，我們早已習(xí)慣了實數(shù)域（\(\mathbb{R}\)）里“倒數(shù)”這一直觀概念：給定一個非零實數(shù) \(a\)，總能找到唯一的數(shù) \(a^{-1}\)，使得 \[a \times a^{-1} = 1. \]二的乘法逆元是二分之一，九的乘 閱讀全文