8.23 Day8

发布时间 2023-08-23 13:50:32作者: Linnyx

10+10+40=60

三题全因为奇怪原因挂分了

被c++进制卡了2天了,我不好说

T1

50->10

0x3f3f3f3f在int->long long下不会变大只有1e9

将水栓放一轴,着火点放一轴,水栓与着火点的匹配不会相交(改为不相交会更优),O(n^2)暴力就很显然了

T2

40->10

我们首先证明:

对于:

\[x_i \equiv k\quad(mod\;A*B) \]

等价于

\[x_i \equiv k\quad(mod\;A) \]

那我们对于给出的柿子可以化为

\[x_i^{p_i}\equiv q_i\quad(mod\;n=\prod p_i)\rightarrow x_i^{p_i}\equiv q_i\quad(mod\;p_i) \]

又因为\(p_i\)是质数,所以根据费马小定理

\[x_i^{p_i}\equiv q_i\quad(mod\;p_i)\rightarrow x_i\equiv q_i\quad(mod\;p_i) \]

此时就变成了CRT的裸题

T3

60->40

观察到在\(2^n-1\)空隙时,这个空隙不需要多余的代价,直接用二进制去拼即可

时间复杂度:\(O(log(V))\)