首页 > 其他分享 >数论小记

数论小记

时间:2023-01-26 12:44:35浏览次数:47  
标签:phi frac gcd limits 数论 sum mu 小记

$[n=1]=\sum\limits_{d|n} \mu(d)$

 

若:$F(n)=\sum\limits_{d|n} f(d)$

则:$f(n)=\sum\limits_{d|n} \mu(d) F(\frac{n}{d})$

 

若:$F(n)=\sum\limits_{n|d} f(d)$

则:$f(n)=\sum\limits_{n|d} \mu(\frac{d}{n}) F(d)$

 

$\phi(ab) = \frac{ \phi(a) \phi(b) \gcd(a,b) } { \phi(\gcd(a,b)) }$

 

标签:phi,frac,gcd,limits,数论,sum,mu,小记
From: https://www.cnblogs.com/DitaMirika/p/17067703.html

相关文章

  • 0123 训练小记
    0123训练小记BZOJ2159Crash的文明世界把\(k\)次方用第二类斯特林数拆开,然后换根dp统计即可。时间复杂度:\(O(nk)\)。CF453ELittlePonyandLordTirek每次操......
  • 数论分块(除法分块)
    定义数论分块是个很常见的技巧,常用于计算$$\sum_{i=1}^{n}\left[\frac{k}{i}\right]$$思路原理很简单:设\(t_i\in\{x|x=\left[\frac{k}{i}\right]\}\)我们想办法每次......
  • 《左耳听风》小记随笔 —— 管理设计
    分布式锁必须满足的要求安全性(Safety):在任意时刻,只有一个客户端可以获得锁(排他性)。避免死锁:客户端最终一定可以获得锁,即使锁住某个资源的客户端在释放锁之前崩溃或者网......
  • 数论笔记
    ·质数素数定理:设\(x\geq1\),以\(\pi(x)\)表示不超过\(x\)的素数的个数。当\(x\rightarrow\infty\)时,\(\pi(x)\to\dfrac{x}{\ln(x)}\)质数筛法1.埃式......
  • 数论笔记
    2023/1/18对于任意自然数\(n,m,a>1\),证\((a^m-1,a^n-1)=a^{(m,n)}-1\)证:来自同学$(a^m-a^n,a^n-1)=(a^n(a^{m-n}-1),a^n-1)$\((a^n,a^{(n,m)}-1)=1\)......
  • 数论
    Problem-D-Codeforces大致题意给你一个长度为\(n\)的数列,让你给数列中每一个数都加上一个任意数,使得这个时候数列中的平方数最多并输出平方数的数量显然我们可以......
  • 数论学习笔记(自留向)
    前言数学我的一生之敌(本篇blog基本没有证明,你杠我就是我对,我们不生产知识,我们只是知识的搬运工)(不写证明才不是因为笔者\(\LaTeX\)用得不熟呢)裴蜀定理结论对......
  • 数论
    ......
  • 数论学习笔记
    逆元定义存在$a\timesx\equiv1\pmod{m}$,我们称\(x\)为\(a\)的逆元。完全剩余系假设\(1\toP-1\)都存在逆元,我们则称他为一个完全剩余系。当......
  • Codeforces Round #834 (Div. 3) D. Make It Round(贪心/数论)
    https://codeforces.com/contest/1759/problem/D题目大意:给定一个数字n,要求扩大至多m倍,求最大的并且最多0的数字。input106115431354161005012345264......