19-大数据一班-杨文冠

分类

学习(23) 未归档(1) 练习(1) 题解(137)

/ 注册

TA的专栏 96篇文章 0人订阅

[kuangbin带我飞]专题十五数位DP

11篇文章 896人学习

[kuangbin带我飞]专题十四数论基础

2篇文章 652人学习

8篇文章 754人学习

动态规划入门

7篇文章 926人学习

1篇文章 673人学习

二分图匹配

2篇文章 658人学习

[kuangbin带我飞]专题七线段树

8篇文章 801人学习

3篇文章 750人学习

线段树进阶

3篇文章 663人学习

codeforces补题

32篇文章 882人学习

莫比乌斯反演

6篇文章 581人学习

网络流初步

4篇文章 767人学习

6篇文章 727人学习

2021杭电多校

3篇文章 791人学习

全部文章（共173篇）

F. Lunar New Year and a Recursive Sequence

，求出最小的满足，不存在输出。有原式可知未知。将用原根表示，从而将乘法变成加法，的原根是，则，可得观察可知，的意义同上。这个式子显然能带入快速幂，快速幂主要是求解出的系数，所以将式子带入后就能求出。所以现在问题就变成了求解已知，直接上模板。 code: #include <bits...

BSGS 矩阵快速幂原根

2021-09-17

1 466

261. Discrete Roots

求出的所有解。找到一个特解因为是质数，所以可以求出的质数。因此对于模意义下的任意数有且仅有一个数满足。假设，则，稍加变换，有：然后套用就一定能求出，然后得到原方程的一个特解找到所有解则，对上面的式子，显然有，设，则有 code: #include <bits/stdc++...

BSGS 原根

2021-09-16

1 597

BSGS模板

求解：博客 code: const int maxn=(1<<16)-1; struct HASH{ int v[maxn+1],tot,ed=0; struct node{ int t,p,next; }a[maxn<<1]; ...

BSGS 哈希

2021-09-16

1 490

P2485 [SDOI2011]计算器

对于第一个任务，上快速幂。对于第二个任务，因为是质数，就不需要扩展欧几里得求逆元了，直接快速幂求逆元。对于第三给任务，上。原式：，则，枚举，然后用存起来：。接着从小到大枚举，如果，那么最小的。 #include <bits/stdc++.h> using namespace...

BSGS

2021-09-15

1 515

P4195 【模板】扩展 BSGS/exBSGS

求解：，不一定互质。如果，则存在逆元，直接使用求解。具体的，假设，如果，方程无解。否则，方程同时除以：直到记，于是方程变成：套时，没必要计算出的逆元然后挪到等式右边，只需要在枚举时查找是否存在即可。注意，不排除小于等于的情况，也就是可能说在还没有达到时就有解了，这个需要特判。这题卡...

BSGS

2021-09-15

1 449

P3327 [SDOI2015]约数个数和来自专栏

求解：因子和函数的一个特殊的性质，带回原式,有：预处理筛出函数，然后分块处理询问。 code： #include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn...

莫比乌斯函数莫比乌斯反演数论分块因子和函数

2021-09-14

1 491

P6271 [湖北省队互测2014]一个人的数论

为了方便计算，这里用变量名表示题目中的求解：则原式：自然数幂和是一个次多项式，可以用伯努利数算出系数，不妨记为由伯努利公式得：则原式：令，易知是积性函数，令，则有则 Code: #include <bits/stdc++.h> using namespace...

莫比乌斯函数莫比乌斯反演伯努利公式组合数

2021-09-08

1 448

P1829 [国家集训队]Crash的数字表格 / JZPTAB 来自专栏

求值：易得原式如下：枚举最大公因数：非常经典的式子的化法：式子的后半段出现了互质数对之积之和，考率先单独拿出来,记有：观察上式，前半段可以预处理前缀和；后半段又是一个范围内数对之和，记可以求解。至此：我们可以数论分块求解这部分。回到定义的地方，则原式为：这...

莫比乌斯函数莫比乌斯反演数论分块

2021-09-05

1 503

LCM Sum 来自专栏

求值：易得原式如下： (通常，我们一般会选择将化成来观察) 将原式复制一份得：考虑到，可以将原式改为：式中为了保证有意义，将值为的一项提取出来。两个求和式中分母相同的项可以合并。即：考虑枚举，所以只需要统计的个数，因为，所以,所以满足这个条件的的数量为。故答案为：到这里...

莫比乌斯函数莫比乌斯反演

2021-09-05

1 581

E. Mocha and Stars 来自专栏

如果求解：根据莫比乌斯的一般套路，很容易想到如下转化：即将原式转化为莫比乌斯函数后交换求和顺序。考虑问题二的限制，有：，这部分就是个背包问题，假设表示前个数相加和为的方案数。那么转移方程有：直接转移复杂度是的，注意到等式右边可以用前缀和维护，令，则有：显然只要先用更新，再...

莫比乌斯函数莫比乌斯反演

2021-09-04

1 521