欧拉函数 例题

笔记链接：

https://blog.nowcoder.net/n/d5d1b02f6b3945ad9283d29c41ee1632

例1 仪仗队 / Visible Lattice Points

https://ac.nowcoder.com/acm/problem/20313 - 单测

https://ac.nowcoder.com/acm/problem/51045 - 多测

经典题目。

题意

在网格中，原点 $(0,0)(0,\; 0)$ 为左下角，$(n-1,n-1)(n-1,\; n-1)$ 为右上角。求以原点为一端点，某一格点为另一端点且不经过其他格点的线段条数。

$1\le n\le 4\times 10^{4}1\; \backslash le\; n\; \backslash le\; 4\; \backslash times\; 10^4$，当然本算法可以解决 $1\le n\le 10^{6}1\; \backslash le\; n\; \backslash le\; 10^6$ 的数据。再大就要杜教筛。

思路

显然，除 $(1,0),(0,1),(1,1)(1,0),\; (0,\; 1),\; (1,\; 1)$ 外，点 $(x,y)(x,\; y)$ 能作为线段的另一端点当且仅当 $1\le x,y\le n1\; \backslash le\; x,\; y\; \backslash le\; n$，$x\mathrm{\ne }yx\; \backslash ne\; y$ 且 $\gcd (x,y)=1\backslash gcd(x,\; y)\; =\; 1$。

若 $x>yx\; >\; y$，可将 $xx$，$yy$ 交换，进而只需考虑 的情况，并将结果乘2。

而满足 且 $\gcd (x,y)=1\backslash gcd(x,\; y)\; =\; 1$ 的 $xx$ 的数量，就是 $\phi (y)\backslash varphi(y)$。

故答案为 $3+2{\sum }_{i=2}^n\phi (i)3\; +\; 2\backslash sum\_\{i=2\}^n\; \backslash varphi(i)$。

用线性筛求每个数的欧拉函数，再累加。时间复杂度为 $O(n)O(n)$。

注意省选题的特判：当 $n=1n\; =\; 1$ 时，只有原点一个格点，没有满足要求的线段。

例2

题目

计算：

其中 $1\le n\le 10^{5}1\; \backslash le\; n\; \backslash le\; 10^5$。

思路

令 $d=\gcd (i,j)d\; =\; \backslash gcd(i,\; j)$，则：

而 $\gcd (i\mathrm{/}d,j\mathrm{/}d)=1\backslash gcd(i/d,\; j/d)\; =\; 1$，

令 $a=i\mathrm{/}da\; =\; i\; /\; d$，$b=j\mathrm{/}db\; =\; j\; /\; d$，则 $\gcd (a,b)=1\backslash gcd(a,\; b)\; =\; 1$。我们可以枚举 $aa$ 与 $bb$，再乘以每组数值对应出现的次数。

对于 $a=b=1a\; =\; b\; =\; 1$ 的情况，出现了 $nn$ 次。总和为 $nn$。

对于 $a>ba\; >\; b$ 的情况，确定了 $aa$ 以后，根据性质1，$a\cdot {\sum }_{\gcd (a,b)=1}b=a\cdot \frac{a\phi (a)}{2}=\frac{a^2\phi (a)}{2}a\; \backslash cdot\; \backslash sum\_\{\backslash gcd(a,b)\; =\; 1\}\; b\; =\; a\; \backslash cdot\; \backslash frac\{a\backslash varphi(a)\}\{2\}\; =\; \backslash frac\{a^2\backslash varphi(a)\}\{2\}$。出现了 $\lfloor \frac{n}{a}\rfloor \backslash left\backslash lfloor\; \backslash frac\{n\}\{a\}\; \backslash right\backslash rfloor$ 次。总和为 ${\sum }_{a=1}^n\frac{a^2\phi (a)}{2}\cdot \lfloor \frac{n}{a}\rfloor \backslash sum\_\{a=1\}^n\; \backslash frac\{a^2\backslash varphi(a)\}\{2\}\; \backslash cdot\; \backslash left\backslash lfloor\; \backslash frac\{n\}\{a\}\; \backslash right\backslash rfloor$。

对于 的情况，将 $aa$ 和 $bb$ 交换，即为上一种情况，计算时乘以2。（与例1类似）

最终答案为：

本题不需要整除分块，$O(n)O(n)$ 累加即可，加的时候取模。

例3

目前笔者尚未找到应用性质4的问题，有待补充。