题意：求不定方程：$$\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$$的正整数解 $(x,y)$ 的数目。数据范围： $1\le n\le 10^6$题解：对不定方程变形：$$(x-n!)(y-n!)=(n!)^2$$设 $a=(x-n!),b=(y-n!)$ ,则：$$ab=(n!)^2$$由算术基本定理得：$$n!=\prod p_i^{a_i}$$所以：$$...

题意：树上分组背包。数据范围： $2 \le N \le 3000,1 \le M \le N-1$题解：算法：树形dp类似于01背包，考虑滚动数组优化。将每一个节点视为一个背包，其容量即为其子树大小。使用 $dp[u][i]$ 表示以 $u$ 为根节点的子树中，使用 $i$ 个子节点的最大值。可以得出状态转移方程：$$dp[u][i]=max(dp[u][i],dp[u][i-j]+dp[...

题意：求不定方程组$$ \left\{ \begin{aligned} & (x,a_0) & = & & a_1 \\ & [x,b_0] & = & & b_1 \end{aligned} \right. $$的正整数解的个数。数据范围： $1 \le a_0,a_1,b_0,b_1 \le ...

题意$n$个人会在$t_i$时刻产生接水的想法，若$1 \dots i-1$没有人在排队，那么他会去排队；每个人接水的时间为$p$，求每个人接水完成的时间数据范围：$1 \le n \le 100000,1 \le p \le 10^9,0 \le t_i \le 10^9$题解模拟题用$3$个优先队列，分别储存原序列产生接水想法的人正在排队的人按题意模拟即可#include<iost...

题意给出$n$个数，每次操作可以选择一个数$+1$或$-1$，求$k$次操作后最小极差数据范围：$2 \le n \le 10^5,1 \le k \le 10^{14}$题解为了减小极差，每次肯定是选择最大值$-1$或最小值$+1$，所以先排个序为了快速转移，可以将$a[i]$变为$a[i+1]$（对于前半部分）或将$a[i]$变为$a[i-1]$（对于后半部分）；而当$k$值不足以进行一...

题意求解$$ \left\{ \begin{aligned} & wx+dy=p \\ & x+y \le n \\ & x,y\ge 0 \end{aligned} \right. $$的一组解$(x,y)$数据范围：$2 \le n \le 10^{12},1 \le p \le 10^{17},1 \le d < w...

题意给出一颗树，求所有节点到其各个祖先路径上所有点的$gcd$值之和数据范围：$1 \le n \le 100000,0 \le x_i \le 10^{12}$题解发现节点的值达到$10^{12}$，肯定不能一个个求$gcd$父节点维护的值是可以传给子节点用的，所以可以在$dfs$时记录，但是空间够吗？注意到$gcd$值如果改变，至少$/2$，也就是说一个节点维护的$gcd$最多只有$\l...