[pixiv] https://www.pixiv.net/member_illust.php?mode=medium&illust_id=61632537
向大(hei)佬(e)势力学(di)习(tou)
这已经是第二次系统的学数论了,idy学长讲的好清晰。学得糊怪我。
1 一元一次同余方程
2 二元一次不定方程
3 欧拉定理
4 逆元
5 中国剩余定理
6 Lucas 定理
7 容斥原理
8 卡特兰数
9 各种组合数求法
10 积性函数
11 线性筛
1一元一次同余方程
如何解形如 ax≡b(mod m)的方程
其实,同余方程可以写成另一种形式 ax+mt=b(t为某整数),这样一来就有两个未知数了,用下面的二元一次不定方程解出x即可
然而,还有一种做法
分类讨论
1 gcd(a,m)==1 可以求出在模m意义下a的逆元,两边都乘上逆元即可
2 gcd(a,m)!=1
(1)gcd(a,m)-|b 无解
(2)gcd(a,m)|b 方程每个项都除gcd(包括m),然后执行1步骤
2二元一次不定方程
当我们要解整数方程 ax+by=c 时
根据拓展欧几里得可知 总有x,y满足 ax+by=gcd(a,b),我们希望由此方程*c/gcd(a,b)得出解
令d=gcd(a,b)
1 d-|c 无解,因为无法乘上一个整数
2 d|c 用拓展欧几里得解出x0,y0,再乘上c/d(当然,其中的x0,y0是多解)
3欧拉定理
欧拉函数定义:
phi(n)=|{i∈[1,n]|gcd(i,n)=1}|
即[1,n]中与n互质的数的个数(模n的缩系的大小)
其中有一些性质
1 phi(nm)=phi(n)*phi(m) (gcd(m,n)=1)积性函数
2 phi(n)=n ∏(p|n) (1-1/p) 用于手算
3 n= ∑d|n phi(d) 在一些题目中可以将n化为此形式,会有特殊效果
欧拉定理
if gcd(a,n)=1 , then a^phi(n) ≡ 1 (mod n)
这个定理一般用来求逆元或对指数取膜*(在模意义下,如果指数太大,可以对指数mod phi)
对我来说,这个性质在day2的离散对数和原根有用
欧拉定理还有一个比较有用的扩展
if q>=phi(n) , then a^q≡a^(q mod phi(n)+phi(n)) (mod n)
这样就不需要a与n互质了(然而见识短浅的我并不明白有什么用T_T)
4逆元
在模m意义下,如果gcd(a,m)=1,设b,使得b满足 ab≡1(mod m),则称b为a在模m的逆元
有两种方式求逆元
1 由欧拉定理得,因为gcd(a,m)=1,所以a^(phi(m)-1) *a ≡1(mod m),则a^(phi(m)-1)即为a的逆元。
2 ab≡1(mod m) 可以写成 ab+mt=1的形式,其中b,t是未知数,可以由拓展欧几里得解出b来
这两种方法都二斤八两,一个快速幂带log,一个exgcd带log,不过exgcd通常还是要快点吧?
5中国剩余定理(孙子定理)
(怕还是需要一点篇幅哦,要证明的话)
对于同余方程组 x≡ai (mod mi) (#)
若mi两两互素,设M=∏mi,Mi=M/mi,Ri=Mi^-1(在模mi的意义下的逆元),于是有下面的公式:
x≡∑ai Mi Ri (mod M)(@)
为什么是正确的呢?(这是我为数不多理解原因的定理了。。)
明确一点,只要(@)满足(#),(@)就是正确的
那么,当∑ai Mi Ri 模mi时,Mj(j!=i)必定包含mi,会被模成0,对答案就没有贡献了。Mi虽包含mi,它乘了一个逆元Ri,就为1了,结果方程(@)化简下来就是(#)了
然而两两互素的要求太严格了,有些时候不适用,如果不互素的话。。
可以两两合并
x≡a1(mod m1) ⇒ x=a1+m1*t1
x≡a2(mod m2) ⇒ x=a2+m2*t2
合并后,a1+m1*t1=a2+m2*t2 ,移项后 m1*t1+m2*t2=a2-a1(t是未知数,符号无所谓)即可用扩展欧几里得来求解t1,t2
设d=gcd(m1,m2)
1 d-|a2-a1 ,无解
2 d|a2-a1,解得k1=k10*(a2-a1)/d+k*m2/d,即x=a1+(……)m1,化简得合并后的式子为:
x≡a1+k10*(a2-a1)/d*m1 (mod lcm(m1,m2))(记住就好了)
一直合并下去,只要出现无解就无解,合并到最后就可以得出答案了
6Lucas定理
其中,如果出现n mod p 卢卡斯定理主要用来求n,m很大,但p是小质数(10^6)的组合数
(证明我是真不会,知道就好了吧……实在要知道大佬们的博客也有讲)
7容斥原理
图片很形象对吧,像极了小学奥数题
公式写下来是:
鸽巢原理:把n个鸽子塞进n-1个巢中,那么必有一个巢有至少2个鸽子(通常可以用来分析)
8卡特兰数
先放公式
常见模型:
1、有n对括号括号序列的方案数
2、在一个n*n的棋盘上从左下角走到右上角,每次只能向右或向上,且不能越过对角线的路径数
3、n个节点的满二叉树种类(每个节点都有两个子节点或没有)
4、……
其实卡特兰数的模型都可以转化成:有2种东西A,B,任何时刻A的数量都大于等于B
那么下面就用模型2来辅助理解加记忆(现推)
直接求困难,就转化为 总数-不合法数
不合法的走法必定会经过图中的虚线,其之后的走法可以沿虚线翻折。不合法的方案就是从(0,0)到(3,5)的走法。由组合数我们可以易得一个矩阵的走法数量,相减即可。
所以,遇到有维持一个东西的数量恒大于等于另一个的问题,就可以想到卡特兰数。模型转化能力倒是很需要。
9各种组合数求法
对于不同数据范围的组合数,求法也会不一样,最好全部掌握
1、n<=5000,直接用c(n,m)=c(n-1,m-1)+(n-1,m)【当年的放苹果问题。。】
2、n<=10^6模大质数(超过n),预处理阶乘及其逆元(o(n)),然后直接用c(n,m)=n!/(m!(n-m)!)计算
3、n<=10^18模小质数(不超过10^6),用Lucas定理,转化为上面的问题
4、n<=10^7,模任意数,可以先用线性筛筛出10^7以内的素数,然后对于每个素数,算出其在n!中对应多少次方(o(logn)),然后指数加减,最后取膜。
【在最后放一个用3做的组合数,把2、逆元都包含进去了
10积性函数
f(nm)=f(n)f(m) (gcd(n,m)=1)
常见有用积性函数:
phi(n):欧拉函数
mui(n):Mobius函数值
嘛,对我来说积性就是在求函数的时候可以在线性筛时o(n)求出来
11线性筛
线性筛可以o(n)的时间和空间复杂度内筛出[1,n]之间的所有素数
设一个数a的最小素数因子是p,则保证a只会被a/p筛掉。这保证了它的时间复杂度是o(n)的。
模板要背熟
int prime[N],cntp=0;
bool not_p[N];
void prime(int n){
not_p[1]=1;
for(int i=2;i<=n;i++){
if(!not_p[i])
prime[++cntp]=i;
for(int j=1;j<=cntp&&i*prime[j]<=n;j++){
not_p[i*prime[j]]=1;
if(i%prime[j]) break;
}
}
}
筛积性函数的话就结合其性质穿插到里面就好了
好啦,就是这样啦
总结:
虽然是基础,但也不能忽略,基础牢固了,才可以衍生出更多的东西
最后,放一道考试题(组合数)
最近Mr. Hu 得到了一个宝箱, 但宝箱被上了锁, 需要解决一个问题才能将其打开, 问题是这样的:
你有n 个不同的苹果, 你想从里面选出m 个来, 问方案数, 结果可能很大, 输出模M 后的结果输出, 其中
M 是k 个不同的素数p1; p2; :::; pk 的乘积.
Mr. Hu 一眼就解决了这个问题, 但他知道你们最近才学了这方面的知识, 于是就把这个问题交给了你们.
Input
第1 行,3 个整数n m k, 意义如上。
第2 行k 个不同的素数:p1 p2 ::: pk.
Output
输出一个整数表示答案.
Sample
treasure.in treasure.out
9 5 2
3 5
6
Note
• 对于10% 的数据,1 n 103,k = 1;
• 对于30% 的数据,1 n 105,k = 1,n • 对于60% 的数据,1 n 1018,k = 1;
• 对于100% 的数据,1 n 1018, 1 k 10
• 对于所有数据,0 m n 1018, 2 pi 105 且pi 互不相同.
#include
#include
#include
#define ll long long
using namespace std;
const ll N=100000+5;
ll n,m,k,p[20],M=1,mod;
ll jiec[N],niy[N];
ll ans[N],fans=0;
ll mult(ll a,ll b){
ll rt=0;
for(ll i=b;i>0;i>>=1,a=(a+a)%mod)
if(i&1) rt=(rt+a)%mod;
return rt;
}
void exgcd(ll a,ll b,ll &x,ll &y){
if(b==0){
x=1,y=0;
}else{
ll x0,y0;
exgcd(b,a%b,x0,y0);
x=y0;
y=x0-(a/b)*y0;
}
}
ll get_niy(ll a){
ll x,y;
exgcd(a,mod,x,y);
x=((x%mod)+mod)%mod;
return x;
}
void init(){
jiec[1]=1;
niy[1]=1;
for(ll i=2;i<=N;i++){
jiec[i]=(jiec[i-1]*i)%mod;
niy[i]=get_niy(jiec[i])%mod;
}
}
ll getans(ll a,ll b){
return mult((mult(jiec[a],niy[b])%mod),niy[a-b])%mod;
}
ll lucas(ll a,ll b){
if(a==b||b==0) return 1;
if(areturn
}