本文作者潘恺璠参加过清北学堂NOIP2017训练营提高组精英班，笔记非常详细。特分享给大家！基本数论相关笔记较多，为方便大家阅读，我们预计会分为三到四篇文章介绍给大家。

点击一下标题可查看其他相关笔记！

NOIP训练营集训笔记—基本数论（一）

NOIP2019年冬令营正在报名中，寒假和元旦都会开课，欢迎大家咨询报名！欢迎咨询报名NOIP2019冬令营！<-点击查看

基本数论（二）

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)

经典例题：给定数a、b、p，求a x ≡b(mod p)的最小正整数解x。

BSGS算法——“北上广深算法”或“拔山盖世算法”：

令x=im-j,m=⌈sqrt(p)⌉,则aim-j≡b(mod p)，

移项，有：(am)i≡baj(mod p)

首先，从0~m枚举j，将得到的baj的值存入hash表；

然后，从1~m枚举i，计算(am)j，查表，如果有值与之相等，则当时得到的im-j是最小值。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<cmath>

using namespace std;

long long a,b,c,m,f[10000000];

map<long long,int> mp;

long long qsm(long long x) //快速幂

{

long long sum=1;

long long aa=a;

while(x>0)

{

if(x&1)

sum=(sum*aa)%c;

x=x>>1;

aa=(aa*aa)%c;

}

return sum;

}

int main()

{

mp.clear();//删除map中的所有元素。

while(scanf("%lld%lld%lld",&c,&a,&b)!=EOF)

{

mp.clear();

if(a%c==0)//判断a,c 是否互质，因为c 是质数，所以直接判断是否整除即可

{

printf("no solution\n");

continue;

}

int p=false;

m=ceil(sqrt(c));

long long ans;

for(int i=0;i<=m;i++)

{

if(i==0)

{

ans=b%c;

mp[ans]=i;

continue;

}

ans=(ans*a)%c;

mp[ans]=i;

}

long long t=qsm(m);

ans=1;

for(int i=1;i<=m;i++)

{

ans=(ans*t)%c;

if(mp[ans])

{

int t=i*m-mp[ans];

printf("%d\n",(t%c+c)%c);

p=true;

break;

}

}

if(!p)

{

printf("no solution\n");

}

}

}

经典例题：求[l,r]之间的所有素数，1≤l≤r≤10 9 ，r-l≤10 5 。

三个解法：

①Miller-Rabin

②线性筛

③SPOJ PRIME1

二、概率：

一些定义和推论：

①Pr[i]表示事件i发生的概率

②Pr[1]+Pr[2]+…Pr[N]=1

③xi表示事件i的权重（自己定义的权重）

④事件xi的期望E[xi]=Pr[i]×xi（i:1~N） 期望=概率×权重

⑤对于独立事件i和j，Pr[i^j]=Pr[i]×Pr[j]，事件i和j的期望是可加的

⑥当事件j已经发生时，事件i发生的概率为：Pr[i|j]=Pr[i^j]/Pr[j]

一个有趣的结论：当太阳已经从东边升起N天后，第N+1天从东边升起的概率：(N+1)/(N+2)。

1.Problem 1：

在小葱和小泽面前有三瓶药，其中有两瓶是毒药一瓶是可乐，每个人必须喝一瓶。

小葱和小泽各自选了一瓶药，小泽手速比较快将药喝了下去，然后就挂掉了。

小葱想活下去，他是应该喝掉手上这瓶药，还是喝掉另外一瓶呢？

我们把瓶子编号为1、2、3，1、2号药是毒药，3号药是可乐。

根据全排列的知识，我们列出6种情况：

1、2、3；1、3、2；

2、1、3；2、3、1；

3、1、2；3、2、1；

由于第一个人是被毒死了，所以只可能是1、2、3；1、3、2；2、1、3；2、3、1；这四种情况，我们发现第二个人喝的是解药的概率为：Pr[是解药]=(1+1)/4=50%。

更简单的想法：小葱选哪个都一样，因为小葱不知道哪个是毒药哪个是可乐。

钟神：显然无所谓！

2.浅谈玛丽莲问题：

美国某娱乐节目的舞台上，台上有三个门，其中一个门后边有汽车，另外两个门后边是山羊，主持人让你任意选择其中一个，然后他打开其余两个门中的一个，你看到的是山羊，这时，主持人会让你重新选择，那么你会坚持原来的选择还是换选另外一个未被打开过的门呢？

分两种情况讨论：

①不换门：抽中汽车的概率是1/3。

②换门：我们编号三个门分别为1、2、3，分别对应羊、羊、车

情况1：假设你第一次猜的那个门是1，主持人必将打开2，选择换门3必能得到车。

情况2：假设你第一次猜的那个门是2，主持人必将打开1，选择换门3必能得到车。

情况3：假设你第一次猜的那个门是3，主持人会打开1或2，你会换1或2号门，得不到车。

综上所述：换门抽中汽车的概率为2/3。

Pr(换门)>Pr(不换门)，所以应该换门！

现在思考：同样是二选一，为什么概率会不同？

因为主持人知道哪个门是羊哪个门是车，上一题中小葱不知道哪瓶是毒药，因为主持人从中作祟，所以概率不同！

3.Problem 2：

小胡站在原点，手里拿着两枚硬币。抛第一枚硬币正面向上的概率为p，第二枚正面向上的概率为q。

小胡开始抛第一枚硬币，每次抛到反面小胡就向x轴正方向走一步，直到抛到正面。

接下来小胡继续抛第一枚硬币，每次抛到反面小胡就向y轴正方向走一步，直到抛到正面。

现在小胡想回来了，于是他开始抛第二枚硬币，如果小胡抛到正面就向x轴的负方向走一步，否则小胡就向y轴的负方向走一步。

现在小胡想知道他在往回走的时候经过原点的概率是多少？

根据定理：往x轴走k步的概率为(1-p)x×p，同理于y轴。

我们可以枚举小胡在第一轮中走到的点(x,y)

小胡走到点(x,y)的概率为(1-p)x+y×p2（乘法原理）

小胡从点(x,y)走回原点的概率为qx×(1-q)y×[(x+y)!/(x!×y!)]。

说明：qx×(1-q)y表示前几步都走x步，后几步都走y步的概率，而实际情况是可以交替着走的，所以我们在后面乘上

（也就是[(x+y)!/(x!×y!)]），才能表示从两种情况中选择往x、y之一走的概率。

所以最终的概率为（对所有情况进行求和）：

这个式子很不好求啊！！肆意展示一下数学功底的时候到了！

我们改变枚举量进行化简！过程如下：

其中：

说明：在以上的推理过程中，打"*"的这一步和红框的推理过程：

①打红框这一步推理：

根据二项式定理，有（字丑不要介意；′⌒`）：

类比一下，有a=q,b=(1-q)，所以原式可以化简为(q+1-q)i=1i=1（太™聪明了啊！！）

②打"*"这一步推理：

直接是等比数列求和即可！

4.Problem 2.333333：

小葱想要过河，过河有两条路：

一条路有100个石头，每个石头有1/100的概率会挂掉。

另一条路有1000个石头，每个石头有1/1000的概率会挂掉。

小葱应该走哪条路呢？（请勿使用计算器）

5.Problem 3（这道题太丑被丢掉了）：

小葱在平面上画了很多条平行等间距为l的直线，小葱将长度为1的针投到这个平面上，求针和直线相交的概率？

典型的蒲丰投针问题：

分情况讨论：

①当l≤1：

②当l>1：

6.Problem 4：

小泽在数轴上的0点处，他每次有r的概率向右走，有1-r的概率向左走，求小泽走到-1处的概率为？

解法：如果直接列式求和计算：大量组合数求和！卡特兰数！级数！（mmp看得我想死）

设到达x-1的概率为p，则p=(1-r)×1+r×p×p 第一步向左走到-1的概率+第一步向右走回到-1的概率（往左走两次到-1）

根据上式，变形得：rp2-p+1-r=0，解方程可得到：p=(1±|2r-1|)/2r，因为有绝对值，所以分类讨论2r和1的关系：

经过紧张又激烈的讨论，我们得出一个分段函数（r都可以取）：

7.Problem 5：

小胡有一棵一个点的树，小胡会给这个点浇水，于是这个点会有的概率长出两个儿子节点。

每次长出新的节点之后，小胡又会给新的节点浇水，它们也都有的概率长出两个新的儿子节点。

小胡不希望自己被累死，所以小胡希望知道这棵树的大小是有限的的概率。

解法：这道题和上一题是一毛一样的！

8.经典题1：

给出n行m列矩阵，k次操作，每次操作选取一个子矩阵，子矩阵内的所有矩阵标记，做了k次操作内，被重复标记的标记为已标记。

求：k次操作后，对于左上角坐标为(x,y)的矩形，至少被1个子矩阵包含的概率为多少？

例如：下面一个2×2的矩阵：

当k=1时，有9种标记方法：

而我们总共能够标记1×4+2×4+4×1个矩阵，所以得到的概率为1/9×(1×4+2×4+4×1)=16/9。

推理过程：

假设k=1时，我们来观察一个3×4的矩阵：

要使得A包含这个红色的矩阵B，那么这个矩阵A的左上点和右下点应该在蓝色的区域，这样才能保证完全覆盖红色矩阵。

假设这个矩阵的左上的点为(x,y)，右下的点为(n-x+1,m-y+1)，在这个图形里面总共有：(1+2+3+…+n)=[n×(n+1)×m×(m+1)]/(2×2)个矩阵，并且满足蓝色文字的条件后，矩阵一共有：x×y×(n-x+1)×(m-y+1)个，所以概率为：x×y×(n-x+1)×(m-y+1)/{[n×(n+1)×m×(m+1)]/(2×2)}。

9.经典题2：

有n个点，坐标为(x1,y1)，(x2,y2)，(x3,y3)，…，(xn,yn)，求一个圆，包含这所有的点，并且保证半径最小。

*力暴**解法：枚举三个点，算出圆，把剩下的点全部丢进去判断在不在里面，算法复杂度：O(n4)

优化*力暴**解法O(n3)：

for(int a=1;a<=n;a++)//往已知圆内一个一个地丢点

{

if(!in(p[a])) circle=cir(p[a]);//a不在圆内

circle=cir(p[a]);//构造以a位圆心的圆

for(int b=1;b<=a;b++)

{

if(!in(p[b])) circle=cir(p[a],p[b]);//构造以a、b两点为直径的圆

for(int c=1;c<=b;c++)

{

if(!in(c)) circle=cir(p[a],p[b],p[c]);//构造a、b、c三点共圆的圆

}

}

}

最优雅地优化O(n)：利用C++中的一个函数叫：random_shuffle（随机打乱n个点的顺序），可以将时间复杂度优化到O(n)，怎么样？很神奇很诡异吧？？！

思想就是：随机选三个点形成一个圆，于是接下来的那些的点进入下面两个for循环的概率实际上很小！

欢迎咨询报名NOIP2019冬令营课程！<-点击查看详情

咨询方式：

司老师 18610112920 赵老师 18610112915 高老师18611056259 老师 18611083835 张老师 18610150289

定期推送帐号信息学新闻，竞赛自主招生，信息学专业知识，信息学疑难解答，信息学训练营信息等诸多优质内容的wx公众平台noipnoi