中国剩余定理一、中国剩余定理（CRT）求解同余方程组$$ \left\{ \begin{aligned} & x \equiv a_1 \ (\bmod \ m_1) \\ & x \equiv a_2 \ (\bmod \ m_2) \\ & \dots \\ & x \equiv a_n \ (\bmod \ m_n...

BSGS(Baby Step Giant Step)算法一、BSGS算法求解高次同余方程$$A^x \equiv B \ (\bmod \ C)$$其中 $(A,C)=1$1.求解令 $x=im+j$此时方程转化为$$A^j \equiv B \cdot A^{-im} \ (\bmod \ C)$$首先对 $i \in [1,m-1]$ ，计算出 $A^i \% C$ 并将其存入hash表...

0/1分数规划一、分数规划给出若干二元组 $(v_i,c_i)$ ，要求从中选出一些，使得 $\frac{\sum v_i}{\sum c_i}$ 最大（最小）。二、解法先考虑最大，最小同理。1、二分法假设问题的最优解为 $ans$ ,则有$$\frac{\sum v_i}{\sum c_i} \le ans$$移项$$\sum v_i \le ans \cdot \sum c_i$$$$\...