点击一下标题可查看其他干系条记！
清北学堂（提高组精英班）集训条记——图论（上）
清北NOIP演习营集训条记——图论（下）（提高组精英班）
NOIP演习营集训条记—信息学根本算法（倍增与分治算法）
NOIP演习营集训条记—信息学根本算法（贪心和搜索算法）
NOIP2019年冬令营正在报名中，寒假和元旦都会开课，欢迎大学咨询报名！
欢迎咨询报名NOIP2019冬令营！
<-点击查看
基本数论（一）
这是一个很大的专题同时也很主要，以是我十分再十分仔细地写这个条记，以是有点慢大家别介意。废话不多说进入正题！
一、数论（研究整数性子的东西）：
1.数论的分类（来自百度百科）：
初等数论、解析数论、代数数论、几何数论、打算数论、超越数论、组合数论、算术代数数论。
2.数：
整数、自然数（大于即是0的整数）、正整数（大于0的整数）、负整数、非负整数、非正整数、非零整数、奇数 偶数。
3.Problem 3：
设N为奇数，a1,a2,…,aN为1,2,…,N的一个排列，求证：(a1-1)(a2-2)…(aN-N)≡0(mod 2)。
证明：由于a1,a2,…,aN为1,2,…,N的一个排列，以是a1+a2+…+aN=1+2+…+N，移项，得：(a1-1)+(a2-2)+…+(an-N)=0为偶数，以是(a1-1),(a2-2),…,(an-N)中必定有至少一项为偶数，以是(a1-1)(a2-2)…(an-N)为偶数,即：(a1-1)(a2-2)…(aN-N)≡0(mod 2)。
4.整除性：
设a,b∈Z，如果存在c∈Z并且a=bc，则称b|a（b为a的因子，“|”表示“能整除”）
5.质数：
如果一个数，只有1和自身作为因子的数，叫做质数（素数）。
通论1：存在一个质数p，若p|ab，则p|a或者p|b。
通论2：若p|a或者(p,a)=1（p和a的最大公因子为1），则p|a2 可以推出 p|a。
通论3：用π(x)表示不超过x的质数的个数，可以证：limπ(x)lnx÷x=1，换种普通说法便是：1~x的质数个数大约为x/lnx（证明韶光繁芜度时可以用）。
6.Problem 3.141：
求证：当n为合数时，2n-1为合数。
证明：由于n为合数，我们可以令n=ab，则2n-1=(2a-1)·(2n-a+2n-2a+2n-3a+…+2a+1)，原式得证。
还可以看出平方差公式是这个的一个特例。
7.质数的剖断：
（1）一个很多人都在用的办法（判断一个较小的数是否为质数）：
bool prime(int x)//判断质数 韶光繁芜度：O(sqrt(x))，最多1012~1014
{
if(x<2) return false;
for(int a=2;aa<=x;a++)
{
if(x%a==0) return false;//不是质数
}
return true;//是质数
}
（2）利用费马小定理：
p为一个素数且p不是a的倍数，则有：ap-1≡1(mod p)（不能从右边推到左边）
做法：多次选取a考验p是否知足费马小定理（解释p可能是质数，选的知足条件的a越多，p为质数的可能性越大）。
韶光繁芜度为：O(klogp)，选取k个a，判断的过程用掉logp，总的加起来为klogp。
特殊地，这样的算法有缺陷，由于有Carmichael数的存在，可导致上述算法给出一个缺点的判断，例如：561、1105、1729，这三个数知足费马小定理，但是它们都是合数！
这里给出1~10000的Carmichael数：561、1105、1729、2465、2821、6601、8911。
（3）Miller-Rabin算法（判断一个很大的数是否为质数）：
由于Carmichael数的存在，并且Carmichael数是有无穷多个的，那怎么办？打表？肯定弗成啊！
以是就要加强这个算法！
如果n为素数，取a<n，令n-1=d×2r，则要么ad≡1(mod n)，要么存在一个数i知足：0≤i＜r，使得：ad×2^i≡-1(mod n)，“一个数mod n=-1”可以表示为：“一个数mod n=n-1”，同样地也是不能从右边推到左边。
韶光繁芜度：O(klogn)
做法：多次选取a考验p是否知足，则是质数的概率就大。（有个好：不存在Carmichael数这样的分外情形！
）
例如：12=322
int a[5]={3,7,11,23,37}//这里选了钟神喜好的5个质数来考验是否知足条件，如果不足保险的话还可以多加几个
bool Miller_Rabin(int n)//从a[]中选出5个a
{
n-1=d2^r;//用n-1来确定d、r
for(int j=1;j<=5;j++)//这里用了5个小于n的质数a来考验，用质数是由于效果更好！
{
if(pow(a[j],d)%n!=1)//不知足第一个条件，pow为快速幂函数，pow(a,b)打算a^b
{
for(int i=0;i<r;i++)
{
if(pow(a[j],d2^i)%n==-1) return true;//第二个条件
}
return false;
}
}
}
（4）筛法（处理1~n区间内有哪些质数）：
基本做法：给出要筛数值的范围sqrt(n)，找出 sqrt(n)以内的素数p1,p2,p3,…,pk。先用2去筛，即把2留下，把2的倍数剔除掉；再用下一个素数，也便是3筛，把3留下，把3的倍数剔除掉；接下去用下一个素数5筛，把5留下，把5的倍数剔除掉；这样不断重复下去……
①非线性筛法；
bool not_prime[1000000];//true表示不是质数，false表示是质数
not_prime[1]=true;//1不是质数
for(int a=2;a<=n;a++)
{
for(int b=a+a;b<=n;b+=a)
{
not_prime[b]=true;
}
}
韶光繁芜度：(1/1+1/2+1/3+1/4+…+1/n)n=nlogn
下面给出了优化版筛法，韶光繁芜度为：nlog(logn)
算法思路：如果当前这个数是合数，之前已经列举过比它小的因子，在列举这个小因子的时候，已经把这个合数的倍数覆盖掉了，以是没必要。
bool not_prime[1000000];//优化版非线性筛法
not_prime[1]=true;//1不是质数
for(int a=2;a<=n;a++)
{
if(!not_prime[a])//如果是质数，进入循环，是合数就不进入
{
for(int b=a+a;b<=n;b+=a)
{
not_prime[b]=true;
}
}
}
②线性筛法：
算法思路：每个合数都由它最小的质因子筛掉（代码第12行）。一个合数会被拆成几个质因子相乘，利用最小的质因子就可以把这个合数筛掉了，避免了重复筛的过程。
int not_prime[1000000];
int prime[1000000];//质数表
int prime_count=0;//质数的个数
memset(not_prime,0,sizeof(not_prime));
not_prime[1]=true;//1不是质数
for(int i=2;i<=n;i++)
{
if(!not_prime[i]) prime[++prime_count]=i;//把i放入质数表prime[]中
for(int j=1;j<=prime_count;++j)//列举质数表中的每一个数
{
if(prime[j]i>n) break;
not_prime[prime[j]i]=true;//翻倍，一个数×另一个数一定为合数
if(i%prime[j]==0) break;
}
}
韶光繁芜度：是线性的，靠近于O(n)。
8.最大公因数：
（1）欧几里得算法（辗转相除法）：
事理什么的我就不说了，看代码YY一下就知道啦（详见人教版高中数学必修三）。
int gcd(int a,int b)//欧几里得算法 韶光繁芜度：O(loga)
{
if(!b) return a;
else return gcd(b,a%b);
}
int gcd(int a,int b)//简化版欧几里得算法 韶光繁芜度：O(loga)
{
return b?gcd(b,a%b):a;//一行代码便是爽
}
（2）扩展欧几里得算法：
用来在已知的a、b中求解一组x、y，使得ax+by=gcd(a,b)成立（根据数论干系定理，这组解一定存在）
求解过程（引自P2O5 dalao的blog：http://p2oileen.xyz/index.php/2017/06/07/exgcd/）：
设a>b，则有当b=0时，gcd(a,b)=a，此时x=1，y=0。
当ab≠0时，设ax1+by1=gcd(a,b)，由于gcd(a,b)=gcd(b,a%b)，则一定有：bx2(a%b)y2=gcd(b,a%b)=gcd(a,b)=ax1+by1
以是将bx2+(a%b)y2=ax1+by1移项+整理可得：
ax1+by1=bx2+(a-(a/b)b)y2=ay2+bx2-(a/b)by2;
根据恒等定理：x1=y2; y1=x2-(a/b)y2;
这样我们就可以通过x2,y2递归求解x1,y1辣！
在gcd不断递归求解的过程中，总会有一个时候b=0，以是递归是有终止条件的。
递归代码如下：
int Ex_Gcd(int a,int b,int &x,int &y)
{
if(b==0)
{
x=1;
y=0;
return a;
}
int ans=Ex_Gcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/by;
return ans;//返回a、b的最大公约数
}
9.中国剩余定理（求解一次同余式组）：
原问题：有物不知其数，三三数之剩二，五五数之剩三，七七数之剩二，问物几何？
大略地来说：有一个数x≡a1(mod p1)，x≡a2(mod p2)，x≡a3(mod p3)，…，x≡ak(mod pk)，求解一个最小的x。
根据问题，我们可以得出好多好多好多的方程：
x=k1p1+a1；x=k2p2+a2；……
两个方程为一组，解之：
k1p1+a1=k2p2+a2移项得：k1p1-k2p2=a2-a1；
在我们小学的时候，就打仗了一个这样的解法，很大略很实用，现在就来仿照一下！
大数翻倍法（一种求解最小公倍数的方法）：
举个栗子：
如哀求两个数的最小公倍数，则将较大数翻倍，一贯翻倍到是较小数的倍数时那么这个数便是这两个数的最小公倍数。
如：6和7
7×1=7,7×2=14,7×3=21,7×4=28,7×5=35,7×6=42
42是6的倍数，那么42便是6和7的最小公倍数。
这个算法的基本思想便是：找到一个最大的ans，然后不断翻倍，使它能够整除其他所有的p
我们假设p1<p2，有：
//大数翻倍法 韶光繁芜度：O(min(p1,p2))
int fanbei(int a1,int p1,int a2,int p2)//p1<p2
{
ans=a2;
while(ans%p1!=a1) ans=ans+p2;
return ans;
}
根据ans=a2+p1p2≡a2(mod p1)，打算得出韶光繁芜度为O(min(p1,p2))，也便是说加p1次一定会找到一个解！
10.逆元：
定义：如果gcd(a,m)=1且存在唯一的b使得a×b≡1(mod m)且1≤b＜m，则b为a在模m意义下的逆元，a、b互为逆元。
举个栗子：令a=3，m=7，我们希望找到一个b知足a×b≡1(mod m)且1≤b＜m，不难找到b=5。则5为3在模7意义下的逆元，3、5互为逆元。
逆元的浸染：在模的意义下做除法，举个栗子：打算(3×6÷3)mod7的结果，按照一样平常的顺序可以算出原式=(18÷3)mod7=6mod7=6。我们利用模的性子，可以把原式变为：(((3×6)mod7)÷3)mod7=4÷3mod7。我们创造进行到这里就无法计算了（模意义下不能做除法），这时候就要用到逆元，3的逆元为5，以是原式\"大众4÷3mod7\公众变为\公众4×5mod7\"大众，打算得6。
探求逆元的方法：
①费马小定理：ap-1≡1(mod p)，p为质数，求a的逆元（担保a和p互质）？
两边同除以a得：ap-2≡1/a(mod p)，也便是说，任意一个数a在模质数p意义下的逆元便是ap-2。
②欧拉定理：aφ(m)≡1适用于任何数m，但要担保gcd(a,m)=1，解法和费马小定理相同，φ(m)的意义之后会讲。
11.积性函数：
定义：如果对付gcd(n,m)=1，有f(nm)=f(n)f(m)，则称f为积性函数，例如f(x)=1便是积性函数。
给出一些经典的积性函数：
①σ(n)=Σd|nd：n的所有因子之和
②τ(n)=Σd|n1：n的因子个数
③μ(n)莫比乌斯函数，稍后会讲（详见13点）
④φ(n)欧拉函数：1~n当中与n互质的数的个数，例如φ(6)=2，下面先容用大约O(n2)的方法求1~n的所有数的φ(ai)：
假设一个数n，求φ(n)？由于n=P1k1·P2k2·…·Prkr → φ(n)=n·(P1-1)/P1·(P2-1)/P2·…·(Pr-1)/Pr。
举两个例子：
30=235，以是φ(30)=30(1/2)(2/3)(4/5)=8。
160=255，以是φ(160)=160(1/2)(4/5)=64。
讲了这么多的函数，怎么样用到积性的性子呢？
积性的意义在于：可以在O(n)的韶光繁芜度内，求出1~n所有数的函数值。
如下的例子（利用在欧拉函数）：我们在O(n)的韶光内求出1~n所有数的φ值
要用到线性筛（其他的函数也是差不多——线性筛中加上函数即可）！
memset(notprime,0,sizeof(notprime)),notprime[1]=true;//初始化
phi[1]=1;//赋初值，φ(1)=1
for(int i=2;i<=n;i++)
{
if(!notprime[i])//是质数
{
prime[++prime_count]=i;
phi[i]=i-1;//如果i是质数，显然和i互质的数有i-1个
}
for(int j=1;j<=prime_count;++j)//求合数的φ
{
if(prime[j]i>n)//考虑prime[j]i这个合数
{
break;
}
not_prime[prime[j]i]=true;
/根据积性函数定义，有φ(prime[j]i)=φ(prime[j])φ(i)，要用积性函数的性子，必须知足prime[j]和i互质/
if(i%prime[j]!=0)//prime[j]和i互质
{
phi[prime[j]i]=phi[prime[j]]phi[i];//直策应用积性函数性子
}
else//i是prime[j]的倍数（不互质）
{
phi[prime[j]i]=prime[j]phi[i];
/把prime[j]i分成prime[j]段，每段长度为i，那么每一段与i互质的数一样多，根据性子：若a与b互质，那么a+b与b互质，a+2b与b互质，以是在第一段和i互质的数加上i之后还和prime[j]互质，以是全体里面就有prime[j]phi[i]个数和它是互质的，以是phi[prime[j]i]=prime[j]phi[i]/
}
if(i%prime[j]==0) break;
}
}
12.卷积（这个我是真的不懂）：
fg=Σd|nf(d)g (n/d)
13.莫比乌斯：
（1）莫比乌斯函数：
含义（三种情形）：拆解一个数n=P1k1P2k2P3k3…Prkr
①若n=1,μ(n)=1 ②当k1=k2=k3=…kr=1时,μ(n)=(-1)r ③前面两个条件都不知足时,μ(n)=0。
意义：容斥事理必备，多有利用到的地方，希望考虑一下吧。
（2）莫比乌斯反演：
以下两个条件等价：
①对付任意正整数n，f(n)=Σd|ng(d)
②对付任意正整数n，g(n)=Σd|nμ(d)f(n/d)
14.一些东西：
①Σd|nφ(d)=n：一个数的因子的φ加起来即是n。
②Σd|nμ(d)=[n=1]：如果n=1，则n的所有因子的μ值和为1，否则为0。
15.欧拉定理：
费马小定理的推广：aφ(m)≡1(mod m)。
补充一些同余的性子：
①反身性：a≡a(mod m)
②对称性：若a≡b(mod m)，则b≡a(mod m)
③通报性：若a≡b(mod m)，b≡c(mod m)，则a≡c(mod m)
④同余式相加：若a≡b(mod m)，c≡d(mod m)，则a±c≡b±d(mod m)
⑤同余式相乘：若a≡b(mod m)，c≡d(mod m)，则ac≡bd(mod m)
（未完待续）
欢迎咨询报名NOIP2019冬令营课程！
<-点击查看详情
咨询办法：
司老师 18610112920 赵老师 18610112915 高老师18611056259 老师 18611083835 张老师 18610150289
定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学演习营信息等诸多优质内容的wx公众年夜众平台noipnoi
