T1

一个数论的题目。

暴力 50pts：

枚举两个区间里面的没一个数字，然后把这个数字分解质因子。如果有某一个质数是 a ~ b 比 c ~ d 的大，那么就是不可以整除。

100 pts：

Legendre's formula 勒让德公式，原谅蒟蒻不会（

Legendre's formula 内容：

\[V_p(n!) = \sum_{k = 1}^{+\infty} [\frac{n}{p^k}] \]

这里面 \(V_p(n!)\) 表示的是一个质数 \(p\) 在 \(n!\) 中出现的次数

所以说上面的题目就可以转化成上面这个公式求解。如果出现了负数，那就说明并不是包含关系，所以我们并不能够整除，所以就判出来了错误情况。

code

for(rl i=0; i < cnt && primes[i] <= max(b, d); ++ i)
    {
        ll tmp = 0, p = primes[i], s = p;
        for(; s <= max(b, d); s *= p) tmp += d / s - (c - 1) / s - b / s + (a - 1) / s;
        if(tmp < 0) {flag = 1; break;}
    }

T2

真没有想到能直接爆搜，想不到，不理解（难受/kl/fn

好了，思路还是要说一下的。因为每一次将这个每个位的和的收敛速度特别快。很像这个题目，我当时还敲了题解。。。结果又出现了然后还是忘了（QAQ）之前做过的类似原题为什么记不住。之前做过的类似原题为什么记不住。之前做过的类似原题为什么记不住。

T3

同学竟然拿树链剖分写过了，赛后一看，真的可以（/lk

yysy，考试的时候想了半天怎么把这个数转化成一个序列，想到中序遍历，但是又想到中序遍历是二叉树的，然后就挂住了（你说我为什么不也敲一个树链剖分，因为之前有一个题吭哧吭哧写了两百行的代码，然后写挂了，直接伤大心，自此之后就发誓模拟赛不敲线段树了）

题目给的 tag 是dp + 贪心，所以我们先从树链剖分说起。（awa

补题的时候又看到一个让我破防的，每一条路径实际上只能走一次，我以为能走多次（寄

solution 1

因为题目中有限制，说了只能是简单路径，他们二者的公共祖先就是两个的端点之一。考场上我想到的是把这一棵树投影成一个序列，然后直接进行计算就好了。（还想了dfs序，可是后面给自己否了。又不愿意写树链剖分，所以就写出来了很荒谬的五个 dfs。。）

对于每一个路径，我们只愿意让它的损耗最小，那么就对于同一个节点来说，长度越小的越优先，对于整个来说也是长度越小越优先，所以我们排个序，然后用一个到不能用为止。之后再去看另外的能不能用。

~~至于树链剖分之后的维护，我们只需要去维护一个区间最小值就好了，表示我们这个区间最多能用多少次，然后把区间最小值归零。~~

所以我们只需要看这一条路径上的最小值是不是满足下面的式子就好了（更简单了（

\[min_{u \to v} \ge 1 \]

T4

好好好，看到官方题解之后人直接裂开，当时赛时想到了用离线做法，但是又双给自己否了。（

暴力想法：对于每一次删边和新建都暴力求一遍桥的数量，得分 25pts。

正解：还没研究会，等我研究好了在更新

526互联

nfls 10.12

T1

T2

T3

solution 1

T4