NOIP訓練營集訓筆記—基本數論（二）
本文作者潘愷璠參加過清北學堂NOIP2017訓練營提高組精英班，筆記非常詳細。特分享給大家！基本數論相關筆記較多，為方便大家閱讀，我們預計會分為三到四篇文章介紹給大家。
點擊一下標題可查看其他相關筆記！
NOIP訓練營集訓筆記—基本數論（一）
基本數論（二）
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，求ax≡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
");
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
",(t%c+c)%c);
p=true;
break;
}
}
if(!p)
{
printf("no solution
");
}
}
}
經典例題：求[l,r]之間的所有素數，1≤l≤r≤109，r-l≤105。
三個解法：
①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循環的概率實際上很小！
推薦閱讀：
