月度归档: 2021年6月

6 篇文章

P2508 [HAOI2008]圆上的整点
Description 题目链接:P2508 求一个给定的圆($x^2+y^2=r^2$)的圆周上有多少个点的坐标是整数。 $r\leq 2\times 10^9$ Solution $$\begin{align}x^2+y^2=r^2 & \Leftrightarrow y=\sqrt{r^2-x^2}\& \Leftrighta…
P5298 [PKUWC2018]Minimax
Description 题目链接:P5298 给定一棵 $n$ 个节点的根节点为 $1$ 的有根树,每个节点最多有两个子节点。 定义节点 $x$ 的权值为: 若 $x$ 没有子节点,则其权值为 $a_i$。若 $x$ 有子节点,则它的权值有 $p_x$ 的概率为其子节点的权值的最大值,有 $1-p_x$ 的概率为其子节点的权值的最小值。 假设 $1…
YbtOJ LCM计数
Description 题目链接:YbtOJ 给定 $T$ 组数据,每组数据给定 $n,m$,求$$\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)[\forall n>1,n^2\not |\gcd(i,j)]$$$1\leq T\leq 10^4,1\leq n,m\leq 4\times 1…
YbtOJ 最小数
Description 题目链接:YbtOJ 109-8 给定一个正整数 $n$,求满足只由 $8$ 组成且被 $n$ 整除的最小数。 有多组数据。 Solution 题目即求满足 $n|88\dots8(k\text{个}8)$ 的最小的 $k$ 值。 转换一下:$$\begin{align}n|88\dots8(k\text{个}8) &…
bzoj4173 数学
Description 题目链接:bzoj4173 设 $S(n,m)$ 为满足 $m \bmod k + n\bmod k \ge k$ 的所有正整数 $k$ 组成的集合,求$$\phi(n)\times \phi(m)\times \sum_{k\in S(n,m)}\phi(k)\bmod 998244353$$$n,m\leq 10^{15…
P3302 [SDOI2013]森林
Description 给定一个 $N$ 个节点的森林,每个点有权值 $v_i$,初始有 $M$ 条边,有 $T$ 个操作: Q x y k 查询点 $x$ 到点 $y$ 路径上的点权种第 $k$ 小,保证合法。L x y 在点 $x$ 和点 $y$ 之间连一条边,保证合法。 强制在线 $1\leq N,M,T \leq 8\times 10^4,…