整点凸包大小

· · 个人记录

感谢传奇特级大师 liuhengxi 的启发性思路

计算 \sum\limits_{i=1}^n\varphi(i) 的量级

令 f(n)=\sum\limits_{i=1}^n\varphi(i),g(n)=n^2

由 g(n)=\sum\limits_{i=1}^nf\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)

可得 f(n)=\sum\limits_{i=1}^n\mu(i)g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)

由容斥原理，可以注意到

\sum\limits_{i=1}^n\mu(i)g\left(\left\lfloor\dfrac{n}{i}\right\rfloor\right)\ge g(1)-\sum\limits_{p\in P\land p\le n}g\left(\left\lfloor\dfrac{n}{p}\right\rfloor\right)=n^2-\sum\limits_{p\in P\land p\le n}\left(\left\lfloor\dfrac{n}{p}\right\rfloor\right)^2\ge n^2-\left(\sum\limits_{p\in P\land p\le n}\dfrac{1}{p^2}\right)n^2\ge\left(1-\sum\limits_{p\in P}\dfrac{1}{p^2}\right)n^2\approx 0.548n^2

所以 \sum\limits_{i=1}^n\varphi(i) 是 O(n^2) 的

计算 \sum\limits_{i=1}^ni\varphi(i) 的量级

令 f(n)=\sum\limits_{i=1}^n\varphi(i),g(n)=\dfrac{n^2(n+1)}{2}

与上面类似的，有 \sum\limits_{i=1}^ni\varphi(i) 是 O(n^3) 的

所以值域为 n 的整点凸包的点数最多为 O(n^\frac{2}{3})