生之、如舟

数论

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

/ 注册

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

Atcoder ABC156_E - Roaming 【组合数学】

E - Roaming 题目描述一共有n个房间，每一个房间里都有一个人，现在有k次移动，某个人从一个房间走到另一个房间为一次移动。问k次移动，n个房间的情况数有多少种？分析这题可以使用枚举空位的做法来做。如果要移动k次，因为最多只能有n-1个空位,所以空位的数量<=min(n-1,k)...

组合数学

2020-02-23

0 797

LightOJ1336-Sigma Function 【打表找规律】

Sigma Function 题目给定一个n<=1e12,求在n之前的正整数，有多少个约数之和为偶数。分析我在题目的公式上看了半天推不出结论来。此题十分适合打表观察规律，所以可以打表看看。打表结果： 1 : odd 2 : odd 3 : even 4 : odd 5 : even 6 ...

找规律

2020-02-22

0 660

LightOJ1245-Harmonic Number (II) 【数学】

Harmonic Number (II) 题目给你上图所以函数，现在要算n<=1e9的结果，共T<=1000组分析我看网上好多人都做成了找规律，其实这是一个数学题，我参考了这位大佬的博客：传送门下面开始以图例方式讲解我们要求的结果其实就是下图中所有竖线的总长度然后我们知道这是一个反...

数学

2020-02-22

1 1255

LightOJ1259-Goldbach`s Conjecture 【素数筛选】

Goldbach's Conjecture 题目 T组询问，每组询问是一个偶数n,验证哥德巴赫猜想回答n=a+b且a，b(a<=b)是质数的方案个数. 分析我们知道1e7之前有不到1e6个质数，所以我们用埃氏筛法预先把质数筛选出来，vis[]保存是否是质数，P[]从小到大保存质数。对于一个...

素数筛选

2020-02-21

0 1199

LightOJ1282 - Leading and Trailing 【快速幂+高中数学】

E - Leading and Trailing 题目给定两个数n,k 求n^k的前三位和最后三位n是int范围，分析求后三位很简单，就是在快速幂的过程中模1000即可。但是求前三位就比较难处理了，用快速幂解决不了。这里我们可以考虑将其转换成double,如果可以转换成double计算，我们只...

快速幂数学

2020-02-21

4 1092

LightOJ1236-Pairs Forming LCM 【唯一分解定理】

Pairs Forming LCM 题目 Find the result of the following code:A straight forward implementation of the code may time out. If you analyze the code, you wi...

唯一分解定理

2020-02-21

4 1257

LightOJ1138-Trailing Zeroes (III) 【找规律+二分】

Trailing Zeroes (III) 题目 You task is to find minimal natural number N, so that N! contains exactly Q zeroes on the trail in decimal notation. As you k...

数学

2020-02-20

0 611

LightOJ1341-Aladdin and the Flying Carpet 【唯一分解定理】

Aladdin and the Flying Carpet 题目给一对数字 a，b ，a是一个长方形的面积，问有多少种整数的边的组合可以组成面积为a的长方形，要求最短的边不得小于b。一共询问T<=4000次分析首先我们把面积进行质因数分解，得所以其因子个数就是此题目的就是让选出合法的...

唯一分解定理

2020-02-20

0 660

LightOJ1370-Bi-shoe and Phi-shoe 【欧拉函数】

Bi-shoe and Phi-shoe 题目给出n个数字的序列a[]，对于每个数字ai找到一个欧拉函数值大于等于ai的数bi，求找到的所有数bi的最小值之和sum 分析这是第二次写关于欧拉函数的题，这是使用了欧拉函数打表的模板，然后再处理一下最优值就可以了，其实也可以排序之后用二分。需要处理...

欧拉函数

2020-02-20

0 554