牛客937992666号

题解

/ 注册

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

题解 | 洛谷P4139 上帝与集合的正确用法 #

定义，可以证明，在某一项后都是同一个值，求这个值 .... 即求解 2 的无限次幂塔模 p，利用扩展欧拉定理递归简化幂运算，同时通过线性筛（欧拉筛）预处理欧拉函数...

2026-01-17

0 16

题解 | 【模板】扩展欧拉定理 #

给定三个正整数，，求，其中快速幂的时间复杂度为，最大为，；先不说可不可能超时的问题，这个数字得用字符串存储，所以快速幂并不能直接解决。正确的解法是使用扩展欧几里得定理欧几里得定理：如果整数与整数互质，则有，其中是欧拉函数，表示到与互质的数的个数 ...

2026-01-16

0 19

题解 | 【模板】扩展欧几里得算法求解乘法逆元 #

对于整数，若存在整数满足：，则称是在模意义下的乘法逆元，记为首先，求解乘法逆元的方法有两种：方法一：费马小定理使用该方法的前提是：必须是质数，并且与互质(不是的倍数) 费马小定理内容：如果是质数，那么对任意与互质的整数，有c成立那么，所以，即可用快速幂...

2026-01-16

0 20

题解 | 【模板】欧拉函数计算Ⅰ ‖ 朴素求值：试除法 #

欧拉函数表示中与互质的数的个数求：首先将经行质因数分解：，其中是不同的质因子那么与互质的数不能被整除，从到一共有个数，那么：第一步：减去能被单个质因子整除的数的个数能被整除的数有个，能被整除的数有个，...，能被整除的数有个所以第一步要减去第...

2026-01-16

0 19

题解 | 动态序列 #

给定长度为的数组，执行两种操作：求解整个序列的第小的值将这个位置上的元素修改为，即每次操作时，输入一个整数，如果，那么执行操作1；如果，则再输入一个整数，然后将的值修改为传统线段树是维护数组下标区间的信息，例如： ...

2026-01-15

0 12

题解 | 区间取反与区间数一 #

给定长度为的字符串(下标范围为)，执行两个操作：区间取反：将这个区间中的全部元素进行取反操作，区间数一：输出下标在这个区间中的所有元素值为的元素的个数，即前面有一道简单的题目是相同的区间取操作+单点查询的值为还是，解决的办法是维护...

2026-01-15

0 16

题解 | 单点修改与区间非平凡异或和 #

给定长度为的数组，执行两种操作：单点修改：将这个位置上的元素修改为，即区间非平凡异或和查询：输出下标在这个区间的所有连续子数列的异或和的异或和，即容易发现的规律：例如: 在连续子序列中出现的次数一共为 (左边数字的个数 + 1)&nb...

2026-01-15

0 14

题解 | 区间增量与区间小于计数 #

给定长度为的数组，执行两种操作：区间增量：将这个区间中的全部元素修改为其与一个数相加后的值，即区间小于计数：输出下标在这个区间中的所有元素中小于一个特定的数的元素的个数，即如果用线段树来做，是维护区间的最大值和区间的和： ...

2026-01-14

0 15

题解 | 区间加乘与单点求值 #

给定长度为的数组，执行三种操作：区间加数：将这个区间中的全部元素修改为其与一个数相加后的值，即区间乘数：将这个区间中的全部元素修改为其与一个数相乘后的值，即单点求值：输出下标为的元素的值对取模后的结果，即基...

2026-01-14

0 15

题解 | many sum #

给定，以及数组的递推式：定义，的意思是能被整除，或者说是的一个因子。例如，，，...... const int N = 2e6 + 10; int n, a_begin, m; in...

2026-01-14

0 17