生之、如舟

数论

动态规划(8) 博弈论(1) 图论(7) 基本算法(29) 并查集(17) 思维(3) 数学(14) 数据结构(5) 最短路(4) 枚举(1) 树状数组(13) 树论(4) 模板(7) 比赛(15) 算法总结(3) 线段树(11) 蓝桥杯(1) 贪心(1)

/ 注册

全部文章 / 数论（共19篇）

唯一分解定理&经典例题【视频讲解】来自专栏

P1072 Hankson 的趣味题视频讲解正在上传B站中代码 #include <iostream> #include <algorithm> #include <string> #include <cstring> #include <...

唯一分解定理

2020-04-08

0 701

兰伯特-切比雪夫定理【数论】来自专栏

首先引用一下百度百科上面贴的定理然后这里给出一道模板题小道消息题目讲解:视频讲解代码 #include <iostream> #include <algorithm> #include <string> #include <cstring> #i...

数学

2020-03-30

0 960

Atcoder_ABC156_F - Modularness 【前缀和】【模运算】

F - Modularness 题意有q组数据，开始给K个数，然后给q组n，x，m让计算出在递推式中，有多少项他在模m之后是小于后一项的。分析这题我参考了这篇博客：传送门我们知道这个递推式就是第0项是x，然后后面依次是上一项加上d，d往后顺延，加完最后一个d，又开始从第一个开始加。很显然，这是...

数学

2020-02-29

0 1051

LightOJ1220-Mysterious Bacteria 【唯一分解定理】

Mysterious Bacteria 题目意思就是给一个数x，现在要将它表示称次方形式，问最高能表示成多少次方？比如： 25 最高能表示成，它的次方形式表示最高是2次方分析这题最开始我写成了二分，按理说是可以过的，但是被WA飞了。好了，现在讲质因数分解做法。我们对N进行质因数分解的：那么如果...

唯一分解定理

2020-02-25

0 705

UVA11426-GCD - Extreme (II) 【欧拉函数】

GCD - Extreme (II) 题目题意很简单，就是给定一个N，让求出N范围内的所有gcd（i,j）的和，时限：10s 分析当我看见这题是时限我就觉得不简单，同时数据量N太大，都到4e6了。但是这题N范围内的答案都需要去求，因为这题没法在线处理，所以考虑暴力的优化。我们需要去枚举什么变量,...

欧拉函数打表

2020-02-25

1 1039

LightOJ1234 - Harmonic Number 【打表】

Harmonic Number 题目分析这题的打表比较有意思，一共有的计算量，这里有3秒的时限，是可以进行几次的的计算的，可是我们没办法开一个的数组来保存每一项的值，所以我们可以每隔50个打一个表，这样我们只需要进行一次的计算，之后次询问，每次我们只需要进行至多50次计算就可以了。 AC代...

打表

2020-02-25

1 779

UVA11752 The Super Powers 【暴力+数学】

The Super Powers 题目若x可以表示成两种及以上的幂形式，比如，被成为超级power数，现在让输出范围内的所有超级power数分析有限其实就是unsinged long long 的最大值,大概1e19，我们是无法通过直接暴力枚举的，那么就考虑下是否可以优化，题目说到至少要有2...

数学

2020-02-24

0 730

POJ2478-Farey Sequence 【欧拉函数】

Farey Sequence 题目 F2 = {1/2}F3 = {1/3, 1/2, 2/3}F4 = {1/4, 1/3, 1/2, 2/3, 3/4}F5 = {1/5, 1/4, 1/3, 2/5, 1/2, 3/5, 2/3, 3/4, 4/5}Fn表示分子分母小于等于n不可约的分数，之后...

欧拉函数

2020-02-24

0 675

LightOJ1213-Fantasy of a Summation 【快速幂】

Fantasy of a Summation 题意给你n,K,mod,让你计算上面代码的结果分析这题很明显不能直接暴力，而要从每个元素贡献方面着手，也就是算一下每个元素会被加多少次。举个例子以第二个样例为例：2 3 350001 2 1 2 1 2 1 2第二排的1，上面共有2条路径，下面...

快速幂

2020-02-24

0 623

LightOJ1197 Help Hanzo 【素数筛选】

Help Hanzo 题目 T组数据，每组数据给出a，b两个值，让求a<=x<=b中有多少个x是质数分析可以发现此题的a，b可以到2e9的范围，所以想要把这么大的范围质数筛选完是不可能的，筛质数有个常用的做法就是筛出sqrt(N)的质数，然后再用这些质数去筛后面的质数。所以我们先把...

素数筛选

2020-02-24

0 1074