# ECNU Foreigners

## Problem A

Solved by ultmaster. 01:19 (+)

## Problem B

Solved by kblack. 01:16 (+1)

## Problem C

Solved by ultmaster. 02:56 (+2)

## Problem D

Solved by zerol. 00:59 (+2)

min_25 筛的做法：对于求 $\mu$，第一步是求质数的个数的前缀和，先假装所有质数都是质数，然后对于 $n$ 的质因子，把它们从质数个数前缀和中除名。第二步计算前缀和的时候就按照真实（$f(p^c)=-1$ 当且仅当 $c=1$ 且 $p$ 不是 $n$ 的质因数）的方法计算。

$\begin{eqnarray} f(n,m) &=& \sum_{i=1}^n \mu(im) \\ &=&\mu(m)\sum_{i=1}^n[(i,m)=1]\mu(i) \\ &=& \mu(m)\sum_{d|m}\mu(d) \sum_{i=1}^{\lfloor \frac n d \rfloor} \mu(id) \\ &=& \mu(m)\sum_{d|m}\mu(d) f(\lfloor \frac n d \rfloor,d) \end{eqnarray}$

zerol：min_25 筛的好处是不用思考，但这题好像魔改的有点多（所以玩脱了）。如果 min_25 第一步直接计算（$f(p)$ 的函数值只有 0 或 1，满足完全积性的条件）的话会需要求 $O(\sqrt m)$ 次 1~x 中与 $n$ 互质的数的个数，这部分会算得很慢，所以才要先把所有质数当质数在扣除掉 $n$ 的质因子。

## Problem E

Upsolved by zerol.

zerol：经过讨论一致决定，这锅卡车运输背。

## Problem F

Solved by ultmaster. 00:26 (+)

## Problem G

Solved by kblack. 00:34 (+)

## Problem H

Solved by zerol. 01:16 (+)

## Problem I

Solved by kblack. 00:16 (+)

## Problem J

Solved by kblack. 02:42 (+3)

## Problem K

Solved by zerol. 02:51 (+6)

# One,Two,Three,AK

## Problem B

Solved by oxx1108. 1:38:59(+1)

## Problem C

Solved by oxx1108. 3:15:01(+1)

## Problem D

Solved by dreamcloud. 4:48:53(+3)

$\begin{eqnarray} &f(n,m) = \sum_{i = 1}^m \mu(in) \\ &=& \mu(n)\sum_{i = 1,gcd(i,n) = 1}^{m} \mu(i) \\ &=& \mu(n) \left( \sum_{d | n} \mu(d)\sum_{i = 1}^{\lfloor \frac{m}{d} \rfloor} \mu(id) \right)\\ &=& \mu(n) \left( \sum_{d | n} \mu(d) f(d,\lfloor \frac{m}{d} \rfloor) \right)\\ \end{eqnarray}$

Unsolved.

## Problem F

Solved by oxx1108. 1:00:47(+4)

## Problem H

Solved by dreamcloud. 1:03:30(+)

## Problem I

Solved by oxx1108. 0:22:20(+1)

## Problem K

UpSolved by dream_cloud