积性函数
一般我们只需要考虑定义域在 \(\mathbb{Z}\) 就够了，什么实数，复数都不用管。
如果函数 \(f(x)\) 满足对于任意的 \(a,b\) 且 \(\gcd(a,b)=1\)，都有 \(f(ab)=f(a)f(b)\)。
欧拉函数 \(\varphi(i)\)
\(\varphi(n)\) 定义为大于等于 \(1\) 且小于 \(n\) 且与它互质的数的个数。
\[\varphi(n)=n\times\prod_{i=1}^m(1-\frac{1}{p_i}). \]她是一个积性函数。
\(\text{P2303 [SDOI2012] Longge 的问题}\)
题意：给定 \(n\)，求 \(\sum_{i=1}^n\gcd(i,n)\)。
因为 \(\gcd(i,n)\) 的取值只有 \(n\) 的因数个种，所以不妨枚举 \(\gcd(i,n)\) 然后计算 \(i\) 的个数。如果 \(\gcd(i,n)=k\) 那么意味着 \(\gcd(\frac{i}{k},\frac{n}{k})=1\)，所以满足条件的 \(i\) 的个数为 \(\varphi(\frac{n}{k})\) 。所以枚举因数计算欧拉函数值然后求和即可。
标签：frac,gcd,数论,个数,varphi,学习,积性,笔记,函数 From： https://www.cnblogs.com/LaDeX-Blog/p/18375329/Number-Theory-P1