[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$。

- 阅读剩余部分 -

- 阅读剩余部分 -

[NOI Online #3 提高组] 优秀子序列

给定长度为 $n$ 的非负整数序列 $\{a_n\}$，定义一个子序列 $\{b_i\}$ 是优秀的，当且仅当：$b_i<b_{i+1},\forall i\ne j\ a_{b_i}\text{and} a_{b_j}=0$。
一个优秀子序列的价值为 $\varphi(1+\sum a_{b_i})$，求所有优秀子序列的价值和。
$1\le n\le 10^6,\ 0\le a_i\le 2\times 10^5$。

- 阅读剩余部分 -

$\text{min-max}$ 容斥！

题目链接：[SHOI2002]百事世界杯之旅

- 阅读剩余部分 -

CF1406E Deleting Numbers

交互题。
给定 $n$，则一开始有集合 $S=\{x|x\le n,x\in \mathbb{N}^+\}$，其中有一个特殊值 $x$，你需要通过以下操作找到他。
$\texttt{A}\ a$：询问集合 $S$ 中 $a$ 的倍数个数 $(1\le a \le n)$。
$\texttt{B}\ a$：先询问集合 $S$ 中 $a$ 的倍数个数，然后删去所有还在 $S$ 中的 $a$ 的倍数，而 $x$ 不会被删去 $(2\le a \le n)$。
$\texttt{C}\ a$：回答 $x=a$。
$\texttt{A,B,C}$ 操作的个数和不能超过 $10000$。
$1 \le x \le n\le 10^5$。

- 阅读剩余部分 -