[NOI2016] 循环之美

给定 $x,y,k$。
求分数 $\dfrac{x}{y}$ 的个数满足：$1\le x\le n,1\le y\le m,\gcd(x,y)=1$，且在 $k$ 进制下 $\dfrac{x}{y}$ 是纯循环小数（或者整数）。
$1\le n\le 10^9,\ 1\le m\le 10^9,\ 1\le k\le 2\times 10^3$。

- 阅读剩余部分 -

本来 $\text{NOIP2020}$ 考成那样，就没抱希望进省队，加上我校高二十分强劲，所以已经准备好买 $\text{D}$ 了。

- 阅读剩余部分 -

本人被省选搞无语了，水平较低，若被叉请直接私信 $\text{D}$ 我（bushi）。

- 阅读剩余部分 -

[CTSC2006]歌唱王国

$T$ 组询问，每次给出长度为 $m$ 的序列 $a$。
现在你将生成一个随机序列，字符集为 $1-n$，每次在序列末尾等概率随机一个数。当 $a$ 成为了随机序列中的一个连续子序列则结束随机。
询问随机序列的期望长度。
$1\le T\le 50, 1\le n,m\le 10^5$。

- 阅读剩余部分 -

不知道为啥，最近做到很多和树的直径相关的题目。在这里来记录一下各种 $\text{tricks}$。

- 阅读剩余部分 -