whix

数论

acm(1) codeforces(13) dp(1) java(1) 区域赛真题(2) 图论(20) 字符串(3) 数据结构(4) 未归档(32) 牛客(8) 组合数学(7) 计算几何(1) 题解(9)

/ 注册

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

P4240 毒瘤之神的考验【莫比乌斯反演+各种数学技巧】

毒瘤题题意： T T T 次询问，每次给定 n ...

2020-02-19

0 439

莫比乌斯反演

一.莫比乌斯函数： 1.定义： μ ( d ) ...

2020-02-19

0 499

狄利克雷卷积

定义：即：两个积性函数的狄利克雷卷积仍为积性函数。数论函数是积性及加性函数。运算法则：狄利克雷卷积的时间复杂度： O ( ...

2020-01-28

0 634

Help Hanzo LightOJ - 1197（大区间内的素数数量统计）

首先数据范围太大，一开始我想的是，用欧拉筛处理出1~sqrt(1<<31-1)内的素数，然后枚举[a,b]内的所有数，用预处理的素数进行判断。但一直t。正解：根据b-a<=1e5，所以可以对a和b的不同取值进行分类。先用欧拉筛处理出1e5以内的所有的素数，用vis1数组标记。...

2019-10-30

0 669

Eid LightOJ - 1024(JAVA大数）

java比赛的相关内容学习了一下Java大数的基本操作 System.gc()的用处。 //package vj; import java.util.*; import java.math.BigInteger; public class Main { public static void ma...

2019-10-26

0 475

Harmonic Number LightOJ - 1234（数学题）

为了防止超时，先预处理，把结果每100保存一次，便于查询 #include <bits/stdc++.h> using namespace std; const int N=1e8+5; double sum[1000005]; void init()//先预处理，然后每100存一次 ...

2019-10-24

0 508

Prime Time（素数预处理+精度误差的处理）

浮点数的精度误差，一般用1e-8和1e-6来处理。 #include <bits/stdc++.h> using namespace std; typedef long long ll; int num[10005]; bool check(ll n) { if(n<2)...

2019-10-20

0 397

数论分块及应用

在一类要统计∑f(i) (1<=i<=n)的数学题中，由于f(i)是单调的，故存在x,y∈[i,j]使得f(x)=f(y)。于是只要找到这段区间就可以节省计算区间内每一个函数值的时间开销。时间复杂度大抵是O(sqrt(n))的。牛客——美味果冻：题解 #include <...

2019-10-14

0 414

The Football Season（拓展欧几里得思维题）

总的思路：贪心因为题目中说明了w>d，那么我们可以让y取得最小非负解，那么就可以使得x+y更小，这样就使z有解的可能性最大。第一种解法：暴力根据拓展欧几里得的x,y的通解。可知y的最小非负解的取值范围是0<=y<w，题中w=1e5。那么就可以直接暴力0~w的所有值，看是否满足...

2019-10-14

0 0

数论模板整理！

一： 1.欧几里得求最大公约数 int _gcd(int x,int y) { return y?_gcd(y,x%y):x; } 2.最小公倍数 #include <bits/stdc++.h> using namespace std; int gcd(int x,in...

2019-10-10

0 399