以诚丶

题解

/ 注册

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

题解 | #Sum Gcd#

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

C++ 数学

2025-07-30

1 20

题解 | #生成函数#

裴蜀定理的推广，不会的可以搜索一下，只要保证就行了。 #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 20

题解 | #Fibonacci 前 n 项和#

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

Python3 快速幂动态规划矩阵

2025-07-28

1 25

题解 | #倍集#

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

Python3 数学

2025-07-24

1 32

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

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

Python3

2025-07-24

1 32

题解 | #游游出游#

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

C++ 二分最短路

2025-07-24

1 29

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

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

C++ 线段树

2025-07-22

1 27

题解 | #游游开车出游#

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

Python3 数学

2025-07-22

1 22

题解 | #游游的选数乘积#

提供一种序列分治的思路。还算比较general。首先我们需要知道，0的个数取决于和的个数的最小值。启示我们预处理出每一个数字中5的个数和2的个数。根据的个数来进行排序，然后我们定义如下分治函数,会将区间分割为.那么答案就拆分为计算左右区间之间跨区间的个数，然后分治计算。关键是如何跨区间，由于我...

pypy3 分治数学

2025-07-21

1 31

题解 | #游游的正整数#

分类讨论最多和最少的情况即可。对于最多的情况，我们先贪心的给他分配最小的，设,整除后，同时。如果为0，那么可以整除，最大就是，否则，我们可以将多出来的部分，分配到已经分配好的d个集合中，他们现在全为，那么还能够分配进去的个数最多为。只要m不超过这个数，就能够分配好。对于最少的情况类似，请读者...

Python3 数学

2025-07-21

1 28