# One,Two,Three,AK

## Problem A

Solved by dreamcloud(-2).

## Problem B

Upsolved by dreamcloud.

\displaystyle{ \begin{align}ans &= \sum_{m=1}^n \sum_{d | (X, m)} \mu(d) (\frac{m}{d})^{cnt} \\ &= \sum_{d|X}\mu(d) \sum_{d|m}^n (\frac{m}{d})^{cnt}\\ &= \sum_{d|X}\mu(d) \sum_{i=1}^{\lfloor \frac{n}{d} \rfloor} i^{cnt}\\ \end{align} }

\displaystyle{ \begin{align} S(n) &= \sum_{i=1}^n g(i) \\ &= \sum_{i=1}^n \left(i^{cnt} - \sum_{d|i, d\lt i} g(d) \right) \\ &= \sum_{i=1}^n i^{cnt} - \sum_{i=1}^n \sum_{d|i,d\lt i} g(d) \\ &= \sum_{i=1}^n i^{cnt} - \sum_{d=2}^n \sum_{d | i}^{n} g(\frac{i}{d}) \\ &= \sum_{i=1}^n i^{cnt} - \sum_{d=2}^n S(\lfloor \frac{n}{d} \rfloor) \end{align} }

## Problem C

Solved by oxx1108.

## Problem D

Solved by oxx1108.

## Problem E

Solved by oxx1108.

Unsolved.

Unsolved.

## Problem I

Solved by oxx1108 & dreamcloud & Xiejiadong.

## Problem J

Solved by dreamcloud.

# ECNU Foreigners

## Problem A

Solved by kblack. 00:49 (+)

## Problem B

Upsolved by ultmaster & zerol.

\displaystyle{ \begin{align}ans &= \sum_{m=1}^n \sum_{d | (A, m)} \mu(d) (\frac{m}{d})^x \\ &\overset{(A,m) = D}{=} \sum_{D|A} \sum_{m=1}^n [(A,m) = D] \sum_{d|D} \mu(d) (\frac{m}{d})^x \\ &\overset{m = Dg}{=} \sum_{D|A} \sum_{g=1}^{\lfloor n/D \rfloor} [(\frac{A}{D}, g) = 1] \sum_{d|D} \mu(d) (\frac{Dg}{d})^x \\ &= \sum_{D|A} \left( \sum_{d|D} \mu(d) (\frac{D}{d})^x \right) \left( \sum_{g=1}^{\lfloor n/D \rfloor} [(\frac{A}{D}, g) = 1] g^x \right) \\ &\overset{g = it}{=} \sum_{D|A} \left( \sum_{d|D} \mu(d) (\frac{D}{d})^x \right) \left( \sum_{t|(A/D) } \mu(t) \sum_{i=1}^{\lfloor n/D/t \rfloor} (it)^x \right) \\ &= \sum_{D|A} \left( \sum_{d|D} \mu(d) (\frac{D}{d})^x \right) \left( \sum_{t|(A/D) } \mu(t) t^x \sum_{i=1}^{\lfloor n/D/t \rfloor} i^x \right)\end{align} }

\displaystyle{ \begin{align}S(n) &= \sum_{i=1}^n g(i) \\ &= \sum_{i=1}^n \left(i^x - \sum_{d|i, d\lt i} g(d) \right) \\ &= \sum_{i=1}^n i^x - \sum_{i=1}^n \sum_{d|i,d\lt i} g(d) \\ &= \sum_{i=1}^n i^x - \sum_{i/d=2}^n \sum_{d=1}^{\lfloor n/(i/d) \rfloor} g(d) \\ &= \sum_{i=1}^n i^x - \sum_{i/d=2}^n S(\lfloor \frac{n}{i/d} \rfloor) \\ &= \sum_{i=1}^n i^x - \sum_{i=2}^n S(\lfloor \frac{n}{i} \rfloor) \end{align} }

zerol: 设 $A$ 是必选数字的 gcd，那么当 $A \ne 0$ 时，就是求：

$\displaystyle{ \begin{eqnarray} && \sum_{m=1}^M \sum_{d|(A,m)} \mu(d) (\frac{m}{d})^C \\ &=& \sum_{m=1}^M m^C \sum_{d|(A,m)} \mu(d) d^{-C} \\ &=& \sum_{d|A}\mu(d) d^{-C} \sum_{d|m }^{M} m^C \\ &=& \sum_{d|A}\mu(d) d^{-C} \sum_{k=1}^{\lfloor \frac{M}{d} \rfloor} (kd)^C \\ &=& \sum_{d|A}\mu(d) \sum_{k=1}^{\lfloor \frac{M}{d} \rfloor} k^C \end{eqnarray} }$

$A=0$ 时就是求 $S(M)=\sum_{m=1}^M \sum_{d|m} \mu(d) (\frac{m}{d})^C$，设 $g(n)=n^C$，那么求和式转化为 $\sum_{m=1}^M (f=\mu*g)(m)$。

$\displaystyle{ g(n)=\sum_{d|n}f(d) \\ f(n)=g(n)-\sum_{d|n,d\ne n}f(d) \\ \begin{eqnarray} S(n)&=&\sum_{i=1}^n g(i)-\sum_{i= 1}^{n}\sum_{d|i,d\lt i}f(d) \\ &\overset{t=\frac{i}{d}}{=}& \sum_{i=1}^n g(i)-\sum_{t=2}^{n} S(\lfloor \frac{n}{t} \rfloor) \end{eqnarray} }$

## Problem C

Solved by zerol. 00:50 (+)

## Problem D

Solved by zerol. 00:29 (+)

zerol：方便的做法是把 $a$ 中 2 的幂提取出来。然后 $a^2 + ((a+1)(a-1)/2)^2= (((a+1)^2+(a-1)^2)/4)^2$。

## Problem E

Solved by ultmaster. 02:50 (+1)

Unsolved. (-1)

## Problem G

Solved by zerol. 03:03 (+3)

Unsolved.

## Problem I

Solved by kblack. 00:26 (+1)

## Problem J

Solved by ultmaster. 00:36 (+)