1. UVA11806

分析

定义

$S_1:$ 首行有人的方案数

$S_2:$ 末行有人的方案数

$S_3:$ 首列有人的方案数

$S_4:$ 末列有人的方案数

于是原题即求 $| S_1 \cap S_2 \cap S_3 \cap S_4 |$ 的值。

再定义

$U:$ 不考虑题目限制的摆放方法数

$T_i:$ $U - S_i$

而

$$\begin{aligned} | S_1 \cap S_2 \cap S_3 \cap S_4 | &= | U | - | T_1 \cap T_2 \cap T_3 \cap T_4 | \\ &=| U | - | T_1 \cup T_2 \cup T_3 \cup T_4 | + \sum_{1 \leq i < j < k \leq 4} | T_i \cup T_j \cup T_k | - \sum_{1 \leq i < j \leq 4} | S_i \cup S_j | + \sum_{1 \leq i \leq 4} | S_i | \\ \end{aligned} $$

2. 二元组对数（重点）

题面

给定正整数 $N \geq 2$ ，设 $1 \leq x,y \leq N， x,y \in \mathbb Z$ ，定义 $f(k)$ 表示满足 $\gcd(x,y)=k$ 的有序二元组 $(x,y)$ 的个数。求 $f(1), f(2), \cdots, f(N)$ 的值。

分析

定义 $g(k)$ 表示满足 $k \mid \gcd(x,y)$ 的有序二元组 $(x,y)$ 的个数。 那么我们有

$$g(k)=\sum_{i=1}^{\lfloor\frac{n}{k}\rfloor} f(ik)\\ g(k)=\lfloor\frac{n}{k}\rfloor^2 $$

于是

$$f(k)=\lfloor\frac{n}{k}\rfloor^2 - \sum_{i=2}^{\lfloor\frac{n}{k}\rfloor} f(ik) $$

那么我们只需要从大到小遍历，就可以以 $O(n \log n)$ 的时间复杂度完成。

3. 欧拉函数

题面

我们定义欧拉函数 $ \varphi (n) = | \{ x \in \mathbb Z | 1 \leq x \leq n , \gcd(x,n) = 1 \} | $，给定一个自然数 $x$ ，求 $\varphi (x)$ 。

作业

HDU网址

Cses网址

HDU5201（例题）

P2158

P1447

P3813

HDU5514

Cses2417