主页 · 5

欧拉函数 \varphi(x)，表示 [1,x] 内与 x 互质的数的个数。对于质数 p 显然有 \varphi(p)=p-1。特殊地，\varphi(1)=1。欧拉函数是一个积性函数，对任意互质的数 a,b，都有 \varphi(ab)=\varphi(a)\cdot\varphi(b)。不互质时，如果 x 为奇数，那么有 \varphi(2n)=\varphi(n)。

众所周知的是，欧几里得算法可以用来求解最大公约数。它的核心是一个恒等式 \gcd(a,b)=\gcd(b,a\bmod b)，并且在 b=0 时函数值是 a。C++14 标准提供一个函数 __gcd() 来求解最大公约数，而在 C++17 以后，我们可以使用 gcd() 和 lcm() 函数来求解两个数的最大公约数和最小公倍数。

也就是说任何合数都可以唯一地表示成 p_1^{c_1}p_2^{c_2}p_3^{c_3}\dots p_n^{c_n}=\prod\limits_{i=1}^np_i^{c_i}~(c_i\in\mathbb N_+) 的形式，这条定理在之后的质数筛中有大用。

数位DP是一种基于按位枚举的计数类DP。一般来说，当题目要求对所有符合特殊性质的数字计数（且这些性质可以转化到数位上讨论）、对给定区间内的合法数做统计、数据范围中出现了超大的上界时，就可以考虑使用数位DP来进行求解。