[洛谷题单]欧拉函数与欧拉定理

要好好学数学啊啊啊啊啊啊啊啊啊啊啊啊啊啊

题单链接

P1082 同余方程

就是一个裸的 exgcd,没了。

顺便也当板子存起来(

P2613 【模板】有理数取余

你看题目中就有一个【模板】这两个字,那就肯定是个模板了……

嘛,也当成板子存下来吧(

P2158 [SDOI2008]仪仗队

这题也是非常经典的了

如果设原点是 $(0,0)$,那么只有 $\gcd(i,j)==1$ 的那些人才会被看到,因为之后的人就被他挡住了。

于是答案就是

$$
\begin{eqnarray}
& 1+2\sum\limits_{i=1}^{n-1}\sum\limits_{j=1}^{i}[\gcd(i,j)==1] \\
& = 1+2\sum\limits_{i=1}^{n-1}\varphi(i)
\end{eqnarray}
$$

然后这个就是 $\mathcal{O}(n)$ 的。当然要搞事的话后面那个也可以用杜教筛去做(比如我)。

未完待续

发表评论