首页 > 代码库 > 2017.8.9数论课小结
2017.8.9数论课小结
一、先是一些整除的性质：
?整除：若a=bk，其中a,b,k都是整数，则b整除a，记做b|a。
?也称b是a的约数（因数），a是b的倍数
?显而易见的性质：
?1整除任何数，任何数都整除0
?若a|b,a|c，则a|b+c, a|b-c
?若a|b，则对任意整数c，a|bc
?传递性：若a|b,b|c，则a|c
例1：
?例题：[CF 762A]k-th divisor
?求n的第k小的约数。如果不存在输出-1
?1 ≤ n ≤ 10^15, 1 ≤ k?≤?10^9
分析：这道题显然不能用O(n)次枚举出答案，如果能做到O(sqrt(n))就好了，事实上确实如此，因为每一个数的因数都是成对出现的，所以我们枚举sqrt(n)以内的因数就能得到范围以外的所有因数，将所得答案排序即可.
二、然后是一些质数和合数的性质：
?若大于1的正整数p仅有两个因子1和p，则称p是一个质数（素数）。
?否则，若p>1，则称p是一个合数。
?1不是质数也不是合数
?若n是一个合数，则n至少有1个质因子。因此其中最小的质因子一定不大于sqrt(n)
?质数有无穷多个。不大于n的质数约有n/ln(n)个。
?唯一分解定理：把正整数n写成质数的乘积（即n=p1p2p3...pk，其中pi为质数且单调不减），这样的表示是唯一的。
例2：
?例题：[CF 776B]Sherlock and his girlfriend
?n个点，标号2..n+1，
?给这些点染色，要求若a是b的质因子，则a和b的颜色不同。
?求一种颜色数最少的方案
?n≤10^100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
分析：这个数据范围是吓你的，因为看到这个数据范围根本就无从下手嘛，连O(logn)都跑不过，除非O(1),不过确实是O（1），仔细分析一下，我们只需要2种颜色即可，质数一种颜色，合数一种颜色就可以了，原因就是合数的质因数是质数，而质数没有因数。
关于怎么分解质因数：
void fenjie(int x) { for (int i = 2; i <= sqrt(x); i++) { while (x % i == 0) { if (!vis[i]) { vis[i] = 1; ans[++tot] = i; } x /= i; } } if (x > 1) ans[++tot] = x; }
分析：这个算法的关键有三个：1.如果除以一个因数就把它除尽. 2.记录这个数有没有进入答案. 3.最后可能还剩下一个数，至于为什么能剩下一个数，我们有一个很重要的定理：每一个数的质因数只有一个大于sqrt(n)的，根据唯一分解定律可以很容易证明.
下面是同余和带余除法的相关知识：
?对于整数a,b，b>0，则存在唯一的整数q,r，满足a=bq+r，其中0≤r<b。
?其中称q为商、r为余数。
?余数用a mod b表示。
?若两数a,b除以c的余数相等，则称a,b模c同余，记做a≡b(mod c)。
?性质：a≡b(mod c)与c|a-b等价
?推论：若a≡b(mod c),d|c，则a≡b(mod d)
例3：奶牛分厮：传送门(应用了第五行的性质)
三、下面是一些最大公约数的知识：
?一些性质：
?(a,a)=(0,a)=a
?若a|b，则(a,b)=a
?(a,b)=(a,a+b)=(a,ka+b)
?(ka,kb)=k·(a,b)
?(a,b,c)=((a,b),c)
?若(a,b)=1，则称a,b互质（互素）
?互质的两个数往往有很好的性质
我们来证明一下第三条：
直接证明(a,b) = (a,a+b)很难，但是我们如果能证明a,b的因数和a,a+b的因数完全相同就好了，我们假设任意一个a,b的公因数p,p是a,b的因数，那么p也是a+b的因数，这样完成了从(a,b)向(a,a+b)的推导，至于如何反过来推导，将过程稍加修改一下即可，那么第二个等式也很容易出来了。这个证明利用的是整除的性质和我们的假设：任意的因数。
?例4：[CF 664A]Complicated GCD
?求gcd(a, a+1, a+2, ..., b)
?1≤a≤b≤10^100
分析：这个数据范围还是吓你的，可以很快的知道(a,a+1) = 1,任意两个相邻的正整数的gcd都为1，然后利用最后一条性质即可推出答案为1.至于为什么(a,a+1)=1呢？可以利用欧几里得算法：(a+1,a) = (a,1)= 1.
?例5：[CF 757B]Bash‘s Big Day
?给定n个正整数{ai}
?求一个子集S，满足gcd(S1, ..., Sk)>1，同时|S|尽可能大。
?1≤n,ai≤10^5
分析：一个一个去分解质因数肯定是不行的，但是我们可以利用像dp中的刷表法一样，从已知状态向未知状态扩展，假设我们枚举因数2，我们可以从2开始枚举有哪些数既是2的倍数又是集合中的数，这样我们枚举质数到amax即可，但是这个算法复杂度是O(n^2)的，会TLE,有没有什么优化方法呢？
其实对于这种枚举的优化，我们无非是减少枚举层数或者避免枚举一定不会有解的答案，可以发现，我们只需要枚举当前质因数的倍数就好了，这样才能满足2个条件.这样的话算法复杂度是O(max(ai)*In(max(ai))).
四、欧几里德算法
?又称辗转相除法
?迭代求两数gcd的做法
?由(a,b)=(a,ka+b)的性质：gcd(a,b)=gcd(b, a mod b)
?容易证明这么做的复杂度是O(log n)
?int gcd(int a, int b) { if (b==0) return a; return gcd(b, a % b); }
五、?裴蜀定理：
?设(a,b)=d，则对任意整数x,y，有d|ax+by成立；
?特别地，一定存在x,y满足ax+by=d
?等价的表述：不定方程ax+by=c(a,b,c为整数)有解的充要条件为(a,b)|c
?推论：a,b互质等价于ax+by=1有解
这个定理是为什么不定方程有解的理论依据.
六、扩展欧几里德算法
扩展欧几里得算法主要是用来解决形如ax+by=c这类方程的问题的，考虑怎么解这个方程，利用欧几里得算法，我们可以把原方程变为：
bx‘+(a - pb)y‘ = c,变为a和b的主元方程：ay‘ + b(x‘ - py‘),其中p是a/b得到的商，那么我们就能得到x=y‘,y = x‘-py‘,这样一直计算下去，可以
借助欧几里得算法的结果得到x‘‘=1,y‘‘ = 0,传递上来，就能得到x,y的值.我们可以考虑递归实现这个算法：
int exgcd(int a, int b, int &x, int &y) { if (!b) { x = 1; y = 0; return a; } int r = exgcd(b, a%b, x, y); int t = x; x = y; y = t - a / b*y; return r; }
这只是一组特解，如果我们要求出所有解该怎么办？可以得到一个解系：x = x0 + kb,y = y0 - ka。
不过运用这一个算法有个重要的前提，我们要求解的ax+by=c的c必须等于gcd(a,b),如果不等于该如何处理呢，可以看我的另一篇博客：青蛙的约会：传送门
另外，第一件事要先判断有没有解，利用裴蜀定理即可.
七、逆元
?若ax≡1 (mod b)，则称x是a关于模b的逆元，常记做a^(-1)。
?回忆同余的性质。上式等价于ax+by=1
?如何求逆元？等价于解方程ax+by=1
?因此逆元不一定存在：
存在的充要条件为(a,b)=1
存在的充要条件为(a,b)=1
?推论：p是质数，p不整除a，则a模p的逆元存在。
?结论：在[0,b)的范围内，a关于模b的逆元(若存在)是唯一的。
我来证明一下最后一个结论：如果存在两个逆元x1<x2<b,那么
ax1≡ax2≡1 (mod b) ,利用第一个同余式，a(x2-x1) % b == 0,
b不整除a,那么b整除x2-x1,而x2-x1 < b,所以矛盾，故结论成立.
int inv(int a, int b) { int x, y; exgcd(a, b, x, y); return x; }
八、线性求逆元
如何O(n)求1~n模质数p的逆元？
我们肯定是要用O(1)复杂度来求出每一个数的逆元，那么一定要用到数学公式和之前推导出的值，我们怎么样才能使它强制出现以前计算过的逆元呢？
余数！我们知道余数小于除数，利用这个性质，我们可以得到：p≡0 (mod p) -----> iq+r≡0 (mod p),为了出现i的逆元，消掉r,我们同时乘i^(-1)r^(-1)即可，得到
qr^(-1)+i^(-1)≡0 (mod p),那么i的逆元就等于-qr^(-1).
for (inv[1] = 1, i = 2; i <= n; ++i) inv[i] = (p - p / i) * inv[p % i] % p;
程序里是p-p/i而不是p/i是为了避免负数.
?例6：组合数取模
?回答T次询问
?每次询问C(n, k) mod 998244353(一个质数)
?T≤10^5，0≤k≤n≤10^7
分析：大组合数是一个非常经典的求逆元的问题，我们知道%操作只有+,-,*三种操作，没有除法，但是可以利用逆元处理：a/b mod c = a * b^(-1) mod c,为什么是这样呢,我们把第一个式子乘b*b^(-1),因为1mod任何数还是1，所以等式成立，我们如果要求n^(-1)!,我们可以直接把1^(-1) * 2^(-1)*...*n^(-1),利用线性求逆元即可，因为有多个询问，保存下答案.
九、线性筛
?考虑一个经典问题：求不大于n的所有素数。
?Eratosthenes筛法：
?1.初始时令列表A={2,3,...,n};p=2
?2.枚举所有p的倍数(不包括p)，并在A中删去这些数
?3.令p为A中的下一个数并跳转至(2)。如果不存在下一个则结束。
?4.算法结束时，A中剩下的数为不大于n的所有素数。
这个算法没什么好说的，就是求出补集，然后用全集减去补集就是我们所求的.
int sieve(int n, bool isprime[], int prime[]) { int tot = 0; for (int i = 2; i <= n; ++i) isprime[i] = 1; for (int i = 2; i <= n; ++i) if (isprime[i]) { prime[++tot] = i; for (int j = i + i; j <= n; j += i) isprime[j] = 0; } return tot; }
复杂度O(nloglogn)
例7：求[1,10^7]内的所有素数。内存限制1MB
分析：内存只有1mb开不下这么大的数组，但是只要求一个答案，我们可以分段来做，假设我们分为k段，第i段为[l,r],我们枚举不超过sqrt(r)的素数并筛掉[l,r]的数即可,只是枚举素数总要保存的吧，那么我们用一种比较玄学的方法：保存[1,sqrt(10^7)]的素数，这样如果区间被覆盖在左边，直接就可以得到答案，如果被覆盖在右边，我们也稍微枚举一下就好了.
但是这个复杂度还是太高，能不能做到O(n)呢？其实可以，如果我们能够保证每一个数只被删除一次就可以了，怎么保证呢？我们利用数的最小分解来分析：比如一个数18，它的分解是唯一的，但是分解的数的排列并不是唯一的，比如2*3*3,3*2*3,我们只让它被第一个删除，怎么样才能做到呢？我们每次添加一个比当前已经分解的最小的质数更小的质数，比如已有了3*3,我们就只能添加2,如果已有2*3,我们就不能再继续搜了，为什么呢？如果我们添加一个5，5*2*3可以先被2*3*5搜到,这样被重复搜索了.这个线性筛的本质就是我们强行给它定一个搜索的顺序和限制，使得每一个数只能被删除一次.
int sieve(int n, int f[], int prime[]) { int tot = 0; for (int i = 2; i <= n; ++i) { if (!f[i]) prime[++tot] = f[i] = i; for (int j = 1; j <= tot; ++j) { int t = i * prime[j]; if (t > n) break; f[t] = prime[j]; if (f[i] == prime[j]) break; } } }
这个代码中f[i]就是i被分解的最小质因数，如果我们枚举的素数正好等于f[i],也就不能继续了.
暂且先整理这么多吧，内容实在是太多了，以后我会慢慢更新的.
2017.8.9数论课小结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。