素数筛法|欧拉函数|欧拉筛法 埃氏筛法 详解
定义 欧拉函数是由nnn指向小于等于nnn且与nnn互质的正整数个数的函数,用phi(n)phi(n)phi(n)表示。 example phi(2) = 1,(1) phi(3) = 2,(1,2) phi(4) = 2,(1,3) phi(5) = 4,(1,2,3,4) phi(6) = 2,(1,5) 公式 结论 假设n的质因数分解为p1a×p2b×...×pmkp_1^a \times p_2^b \times ... \times p_m^kp1a​×p2b​×...×pmk​(pip_ipi​是质因数),则欧拉函数可以用公式求得: phi(n)=n×(1−1p1)×(1−1p2)×...×(1−1pm)phi(n) = n \times (1- \cfrac{1}{p_1} ) \times (1- \cfrac{1}{p_2} ) \times ... \times (1-\cfrac{1}{p_m})phi(n)=n×(1−p1​1​)×(1−p2​1​)×...×(1−pm​1​) 推导 首先一个数xxx与nnn互质,说明没有公共的质因子,即xxx不能有 ...
反馈
反馈建议&bug 电子木鱼 Update Log正式版 1.1.0 rp与功德分开存储、更改部分页面布局 1.0.2 添加动画 1.0.1 增加存储数据功能 1.0.0 发布 呆毛无限生长的虹夏! Update Log2023/11/11 0.1.0 测试版发布
Misaka Mikoto
没有视频请刷新页面 你指尖跳动的电光,是我永恒不变的信仰。 唯我超电磁炮永世长存! 君の指先で舞っている电光は,私の一生不変の信仰で,私の超电磁炮だけが永远に生きている! That spark glittering on your fingertips is my unshakeable faith for life! May my Railgun be lasting for eternity! (function(){var player = new DPlayer({"container":document.getElementById("dplayer0"),"loop":true,"screenshot":true,"video":{"url":"https://raw.githubusercontent.com/Genkaim/blog_video/main/data/202308150932146.mp4"},"danmaku":{"id":"46190A32F63DFF2CF0A3BB0F3293636C","api":"https://api.prprpr.me/dp ...
公告
csp已落榜,先更新些应用层面的(单休懒得搞算法),学算法得等高考后了捏
模式切换阅读模式开发者工具