以诚丶

题解

/ 注册

全部文章 / 题解（共26篇）

题解 | #Sumdiv#

首先对于,可以通过质因数分解，求出所有的质因数次数。对于质因数,次数为，由于次方，那么变为。约数和可以这样表示：对于单独的。需要求解这个等差数列的和。由于给出的模数为质数，根据等比数列求和公式。分子下面可以用逆元求得。还有一种精妙的分治法也可以求得，题解区有就不多赘述，代码中也有体现。 //...

C++ 质因数数论

2025-09-25

0 7

题解 | #算法配置#

区间重置线段树的简单应用，这里给出模板，请自行搜索学习： """所有下标都从0开始""" class LazySegmentTree: def __init__(self, n: int): self.n = n self.sum = [0] * (self...

pypy3 Python3 线段树差分数组

2025-09-10

1 13

题解 | #Sum Gcd#

由于互质和唯一分解定理，和是没有相同的质因数。那么可以得出：本题的做法就是，计算出一个总和，然后对于每一个,需要重新计算自己本身，因为和并不互质，不满足等式1，然后加上即可。 #include <bits/stdc++.h> using namespace std; #define ...

C++ 数学

2025-07-30

1 22

题解 | #生成函数#

裴蜀定理的推广，不会的可以搜索一下，只要保证就行了。 #include <bits/stdc++.h> using namespace std; #define close ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL...

C++ gcd

2025-07-30

1 25

题解 | #Fibonacci 前 n 项和#

由题意可知，。也就可以可以通过的后面一项和的后面两项推出来。那么可以得到如下矩阵形式：这个形式就可以通过矩阵快速幂求出。 import sys from collections import Counter from heapq import heappop, heappush from ma...

Python3 快速幂动态规划矩阵

2025-07-28

1 29

题解 | #倍集#

这道题看了其他大佬的题解才看出来，首先就是需要让每一个独立的区间内部没有倍数，这可以通过收缩左边界实现。然后假设全要，这个时候需要的就是找出和没有倍数关系的有几个。我们从开始枚举，我们要满足，也就是乘一个倍数过后，仍然小于d。那么可以反解出k。然后我们又需要让,那么最大的一个数就是,个数就是...

Python3 数学

2025-07-24

1 38

题解 | #游游的k-好数组#

根据间隔分组，也就是和是一组的，然后对于每一个组内元素，由于操作只能够加，不能减，所以所有元素一定会变为最大值。设每一个组的最大值为,个数为,总和为,那么代价为。那么求出所有组的总需求量，如果不够，那么直接返回。然后将扣除后剩下的贪心的全部分给一组，那么就只要枚举组，记录哪一个最大即可。 im...

Python3

2025-07-24

1 38

题解 | #游游出游#

大思路是二分+dijkstra。需要注意到车的重量越小，我们可以走的路越多，越能够到达终点，具有二段性，可以二分。我们可以二分车可以达到的最大重量，假设为,然后对题目给出的图跑dijkstra,注意图的边有效的条件是他的可承受重量小于车的重量。时间复杂度,cpp能跑过，python过不了。 ...

C++ 二分最短路

2025-07-24

1 34

题解 | #游游的整数操作#

本题好像只要用支持区间加，区间重置的线段树也能过，但是不能够在过程中取模？大思路就是，我们给原数组排序，因为每次加减都是在所有数的上面操作，然后加法不会改变顺序，而减法可能会导致从某个位置开始往左全是0，具有二段性，我们可以二分找到这个位置，然后将左边的全部置为0，右边的正常减就行了。由于涉及到...

C++ 线段树

2025-07-22

1 31

题解 | #游游开车出游#

实际上就是求一个这个函数所能够达到的最小值，这个是一个关于的函数，我们可以对他进行求导，让，可以得出如下式子：。 import sys from math import sqrt # 输入加速 input = sys.stdin.readline if __name__ == '__main_...

Python3 数学

2025-07-22

1 26