HNSDFZ2016 #5

# HNSDFZ2016 #5

## A. 微小的数学 (ruanxingzhi)

### 题目描述

—— Gromah

—— ruanxingzhi

$$\sum_{i=1}^n\sum_{d \mid i} \varphi(d) \mu(\frac{i}d)$$

### 样例输入1

 1 13 

### 样例输出1

 1 38 

### 样例输入2

 1 233 

### 样例输出2

 1 10138 

## B. 一圈一圈 (Haogram)

### 题目描述

“有些事,我都已忘记,但我现在还记得,啦啦啦啦啦......”
“一圈一圈似爪牙,似魔鬼的步伐,啦啦啦啦......”

### 样例输入1

 1 2 3 4 5 6 7 8 9 3 1 0 0 6 1 8 7 6 5 2 7 8 1 3 1 

### 样例输出1

 1 2 3 4 YES NO NO YES 

### 样例输入2

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 7 1 1 1 7 1 4 2 3 4 7 5 5 6 1 6 0 4 2 4 4 4 5 3 5 5 3 1 

### 样例输出2

 1 2 3 4 5 6 NO YES NO NO YES YES 

### 数据限制

$7$个数据测试点，限制如下：

$1$ $\le 10$
$2$ $\le 10^3$
$3$ $\le 10^5$
$4$ $\le 2 \times 10^5$
$5$ $\le 10^6$ 左右的边与$y$轴平行，

$6$ $\le 10^6$ 凸多边形
$7$ $\le 10^3$ $0 \le x,\;y \le 10^3$

### 评分标准

$1$ $5$ $0.1\text{s}$
$2$ $10$ $1\text{s}$
$3$ $15$ $1\text{s}$
$4$ $30$ $1\text{s}$
$5$ $10$ $1\text{s}$
$6$ $15$ $1\text{s}$
$7$ $15$ $1\text{s}$

$1$ $\ge 10^5$ $\ge 2\times 10^5$ $\ge 3 \times 10^5$ $\ge 4 \times 10^5$ $\ge 5 \times 10^5$
$2$ $\ge 5 \times 10^4$ $\ge 10^5$ $\ge 2 \times 10^6$ $\ge 3 \times 10^6$ $\ge 4 \times 10^6$
$3$ $\ge 5 \times 10^2$ $\ge 10^3$ $\ge 2 \times 10^5$ $\ge 4 \times 10^5$ $\ge 5 \times 10^5$
$4$ $\ge 10^3$ $\ge 1 \times 10^5$ $\ge 2 \times 10^5$ $\ge 3 \times 10^5$ $\ge 4 \times 10^5$
$5$ $\ge 10^3$ $\ge 8 \times 10^5$ $\ge 10^6$ $\ge 1.2 \times 10^6$ $\ge 1.4 \times 10^6$
$6$ $\ge 5 \times 10^2$ $\ge 8 \times 10^5$ $\ge 10^6$ $\ge 1.2 \times 10^6$ $\ge 1.4 \times 10^6$
$7$ $\ge 10^6$ $\ge 2 \times 10^6$ $\ge 3 \times 10^6$ $\ge 4 \times 10^6$ $\ge 10^7$

## 部分题解

### A

raunxingzhi总是喜欢出这种题目，莫名其妙。

$$f(n) = \sum_{d \mid n} \varphi(d) \mu(\frac{n}d)$$

$$\varphi(n) = \sum_{d \mid n} f(d)$$

$$f(n) = \varphi(n) - \sum_{d \mid n,\;d \lt n} f(d)$$

mdzz，$O(n \ln n)$怎敢过......

$$\sum_{i=1}^n \sum_{d \mid i} \varphi(d) \mu(\frac{i}d) \Longrightarrow \sum_{d = 1}^n \varphi(d) \sum_{k = 1}^{\left\lfloor \frac{n}d \right\rfloor} \mu(k)$$

 1 typedef int int64; 

### B

Haogram的题似乎有很多做法，我都不太记得了，这里瞎BB一下：

### D

60分不写就算了，40分智障分也不写你们好劲啊！一颗赛艇啊！