51nod1355 斐波那契的最小公倍数
51nod LOJ 分析 为了方便,下面简记 $f_S$ 为 $f_{a_1},f_{a_2},\cdots,f_{a_k}$,其中 $S=\{a_1,a_2,\cdots,a_k\}$。 考虑一个经典容斥 从小到大枚举倍数算贡献即可。 实现得好的话时间复杂度是 $\mathcal{O}(n\log n)$ 的。 代码 // ================================...
51nod LOJ 分析 为了方便,下面简记 $f_S$ 为 $f_{a_1},f_{a_2},\cdots,f_{a_k}$,其中 $S=\{a_1,a_2,\cdots,a_k\}$。 考虑一个经典容斥 从小到大枚举倍数算贡献即可。 实现得好的话时间复杂度是 $\mathcal{O}(n\log n)$ 的。 代码 // ================================...
Luogu LOJ 分析 可以发现这两条规则长得很像更相减损术,推一推可以得到 最后那一步可以考虑实际意义,证明就不写了( 如果没有修改的话就可以预处理 $i^2\varphi(i)$ 的前缀和然后数论分块计算了。然而现在还有若干次对于 $f(d,d)$ 的修改,可以想到用一个数据结构来维护。 思考一下,我们在数论分块时需要进行 $\mathcal{O}(Q)$ 次修改和求 $\mathc...
Luogu LOJ 分析 先不考虑 $a$ 的限制,则答案为 这样子可以发现,我们只要把 $\leq a$ 的 $\sigma(k)$ 的贡献设成 $\sigma(k)$、$> a$ 的 $\sigma(k)$ 的贡献设为 $0$ 就可以算出正确答案了。 于是只要把所有询问按 $a$ 排序,然后将 $\sigma(k)$ 从小到大加入即可。 代码 // ===============...
Luogu LOJ 分析 下面都假设 $n\leq m$。 方法一 推出来和上面是一样的。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include &...
Luogu 分析 显然一个置换的步数就是它所有环长的 $\operatorname{lcm}$。于是问题变为求有多少个数 $n$ 的某个拆分中所有数的 $\operatorname{lcm}$。 考虑 DP。设 $dp_{i,j}$ 表示 $i$ 拆成若干个最大质因子 $\leq p_j$ 且不为 $1$ 的数时的答案,不难得到转移 答案即为 $1+\sum_{i=1}^n dp_{n,|...
Festival 考虑差分约束。设 $dis_{i,j}$ 表示 $X_i$ 至多比 $X_j$ 大多少,则 若 $X_i+1=X_j$,则 $dis_{i,j}=-1,dis_{j,i}=1$,连边 $(i,j,-1)$ 和 $(j,i,1)$。 若 $X_i\leq X_j$,则 $dis_{i,j}=0$,连边 $(i,j,0)$。 考虑无解的情况。一种情况是出现负环,另一种情况是...
Codeforces Luogu 分析 首先确定基本的计算方式 则我们需要平方、减法、乘法(除以 $2$ 就是乘逆元)这三种运算。 既然要造计算机,那么一定要先求出一个 $0$ 来。因为 $1+1\times(p-1)\equiv 0\pmod p$,所以可以快速乘一下。 for (int i=p-1;i;>=1) { // 0 -> o[16] if (i&1...
Luogu 分析 这样就很好杜教筛了。 代码 // ==================================== // author: M_sea // website: https://m-sea-blog.com/ // ==================================== #include <bits/stdc++.h> #defi...
Luogu LOJ 分析 显然用来打每条龙的剑是确定的,可以用 std::multiset 预处理出来。假设打第 $i$ 条龙的剑的攻击力为 $atk_i$。 那么如果一个 $x$ 满足条件,则应有 这样子就可以直接 exCRT 了。 需要注意的是 $a_i\leq 10^{12}$,所以需要写慢速乘。 代码 // author: M_sea // website: https:/...
Codeforces Luogu 分析 下文中的 $A$ 为 $\max_{i=1}^n\{a_i\}$。 考虑枚举答案的 $\gcd$,问题变为求满足 $\gcd(x,y)=g$ 的 $x,y$ 中 $x\times y$ 的最大值。 可以考虑贪心。我们先把所有满足为 $g$ 的倍数的数拿出来并从大到小排序,然后依次扫描,同时开一个栈来维护。对于每个数,我们需要判断栈中有没有与它互质的数,...