數學小專題

CSP-S數學專題。這里只會給出公式，但不會有過多的證明。

簡單復習一下數學的幾個模板。
總感覺數學還是要多復習，不然很容易忘記。

簡單數論

\(O(\sqrt{n})\)判定質數

不用多講。

Miller-Rabin算法

bool mr(ll x,ll b)
{
    if(qp(b,x-1,x)!=1)
        return false;
    ll k=x-1;   
    while((k&1)==0)
    {
        k>>=1;
        ll d=qp(b,k,x);//快速冪,計算b^k mod x
        if(d!=1 && d!=x-1)
            return false;
        if(d==x-1)
            return true;
    }
    return true;
}
bool mr(ll x)
{
    if(x==46856248255981)
        return false;
    if(x==2||x==3||x==7||x==61||x==24251)
    return true;
    return mr(x,2)&&mr(x,3)&&mr(x,7)&&mr(x,61)&&mr(x,24251);
}

對于一個數\(x\)，我們選一個質數\(b\)作為基底，依次計算\(b^{x-1},b^{\frac{x-1}{2}},b^{\frac{x-1}{2^2}},\cdots\)。注意：

在第一次計算時不考慮\(b^{x-1} \equiv x-1\)的情況。
遇到\(b^{\frac{x-1}{2^k}} \equiv x - 1\)或者\(\frac{x-1}{2^k}\)為奇數的情況就直接判定正確。

注意\(5\)個素因子積：\(2,3,5,7,24251\)。那個很強的偽素數\(46856248255981\)我倒覺得真心沒必要背。

約數\(O(\sqrt{N})\)篩法

又叫試除法。每次圍繞\(\sqrt{N}\)對稱地找到兩個因子\(p,q\)，把這兩個因子加入約數列表中。注意當\(p^2=N\)時要特判一下，不然會加多了。

倍數法

和線性篩的代碼比較類似，適合一次篩多個質數的問題。

gcd

\[ \gcd(a,b) = \gcd(b, a \mod b) \]

埃式篩

比較好理解。

線性篩

for(rg int i = 1; i <= N; ++ i)
{
    if(v[i] < 0)
    {
        v[i] = i;
        prime[++ pn] = i;
    }
    for(rg int j = 1; j <= pn; ++ j)
    {
        if(prime[j] * i > N || prime[j] > v[i])
            break;
        v[i * prime[j]] = prime[j];
    }
}

暫時還沒有試過這個代碼。從理論上來說應該是沒錯的。

進階數論

冷知識

設一個數的分解式：

\[N = \prod_{i = 1}^{k}p_i^{\alpha_i} \]

我們可以把指數提取出來：

\[N = (\alpha_1,\alpha_2,\cdots) \]

它可以幫助我們從全新的角度觀察數論。其實說白了就是把數論中的運算變成對數形式。

舉個例子，求兩個數的\(\gcd\):

\[\gcd((\alpha_i),(\beta_i)) = (\min\{\alpha_i,\beta_i\}) \]

這樣我們就可以把方程\(\gcd(x,a)=b\)變成若干個整數不等式了。

再舉個例子，整除關系：

\[(\alpha_i) \big| (\beta_i) \iff \alpha_i \leq \beta_i \]

這樣就也把整除關系變成若干個不等式了。從本質上來說，\(<\mathbb{Z}^{*},|>\)本身就是一個偏序集，因此才會有這樣的特性。

可以結合這道題看一下：CSP-S 2009 Hankson的趣味題

重要函數的計算與預處理

歐拉函數\(\phi(n)\)。

int phi(int n)
{
    int ret = n;
    for(rg int i = 2; i * i <= n; ++ i)
        if(n % i == 0)
        {
            ret = ret / i * (i - 1);
            while(n % i == 0)
                n /= i;
        }
    if(n > 1)
        ret = ret / n * (n - 1);//n是質數
    return ret;
}

這個是直接根據定義式計算的。
它的預處理版本：

void init()
{
    for(rg int i = 2; i <= n; ++ i)
        phi[i] = i;
    for(rg int i = 2; i <= n; ++ i)
        if(phi[i] == i)
            for(int j = i; j <= n; j += i)
                phi[j] = phi[j] / i * (i - 1);
}

當然，還有基于線性篩的版本：

void init()
{
    for(rg int i = 2; i <= N; ++ i)
    {
        if(v[i] == 0)
        {v[i] = i, prime[++ pn] = i, phi[i] = i - 1;}
        for(rg int j = 1; j <= pn; ++ j)
        {
            if(prime[j] * i > N || prime[j] > v[i])
                break;
            v[i * prime[j]] = prime[j];
            phi[i * prime[j]] = phi[i] * (i % prime[j] == 0 ? prime[j] : prime[j] - 1);
        }
    }
}

這里用到了\(\phi(i)\)的兩個性質，這里也不多贅述。

莫比烏斯函數\(\mu(n)\)。

for(rg int i = 1; i <= N; ++ i)
    mu[i] = 1, v[i] = 0;
for(rg int i = 2; i <= N; ++ i)
{
    if(v[i])
        continue;
    mu[i] = -1;
    for(rg int j = (i << 1); j <= N; j += i)
    {
        v[j] = 1;
        if((j / i) % i == 0)
            mu[j] = 0;
        else
            mu[j] *= -1;
    }
}

順帶一提，學長zsy講過一個非常有趣的理解方式。這里不妨粘貼之。

我們都知道莫比烏斯反演：（簡便起見，這里直接寫成卷積形式）

\[\begin{aligned} f = I * g\\ g = \mu * f \end{aligned} \]

從之前的素因子式\(N=(\alpha_i)\)的角度理解，\((\alpha_i)\)其實是一個高維向量，而\(g(\alpha_i)\)就是這個向量的點權，\(f(\alpha_i)\)就是\(g\)的前綴和。聯想到二維前綴和\(a_i = S_i - S_{i-1}\)，莫比烏斯反演事實上就是對于高維前綴和\(f(\alpha_i)\)的差分變換。

實際上，我之前補充過一個冷知識：廣義的莫比烏斯反演。對于偏序關系\(\preceq\)，定義它的莫比烏斯函數：

\[\mu(x,y) = \begin{cases} 1 & x = y\\ -\sum_{x \preceq u \prec y} \mu(x,u) & x \prec y\\ 0 & \text{else} \end{cases} \]

則有：

\[\begin{aligned} f(x) &= \sum_{0 \preceq u \preceq x} g(u)\\ g(x) &= \sum_{0 \preceq u \preceq x} \mu(u,x)f(u) \end{aligned} \]

這實際上說明了莫比烏斯反演實質上就是一個局部有限偏序集上的高維前綴和差分變換。這也進一步說明了莫比烏斯函數在容斥原理和數論上的鏈接作用。

模算術

正如你所見，\(a \mod b\)這個函數在設計時出現了一些問題，使得兩個字母之間間隔太大。因此，下文中均用C++寫法\(a\% b\)代表\(a\mod b\)。同理，為了方便書寫，我們統一用\(a/b\)代表\(\lfloor\frac{a}\rfloor\)。

歐拉定理

若正整數\(a,p\)互質，則：

\[a^{\phi(p)} \equiv 1 \pmod{p} \]

對于任意正整數\(b\)，還有：

\[a^b \equiv a^{b \% \phi(p)}\pmod{p} \]

如果\(a\)和\(p\)不一定互質，則應該使用下面這個公式：

\[ a^ \equiv \begin{cases} a^{b\%{\phi(p)}+\phi(p)} & b > \phi(p)\\ a^b & b \leq \phi(p) \end{cases} \pmod{p} \]

證明均略去。

裴蜀定理和exgcd

對于整數方程\(ax+by=c\)，存在整數解\((x,y)\)的充要條件是\(\gcd(a,b)|c\)。它的另一個版本是\(ax+by = \gcd(a,b)\)一定有整數解。
它的證明是基于\(\gcd(a,b)=\gcd(b,a\%b)\)的。在遞歸終點\(b=0\)時，顯然有\(x=1,y=0\)。否則，
根據數學歸納法，假設下面這個方程成立：

\[ bx+(a\%b)y = \gcd(b,a\%b) \]

根據模數的另一種定義：

\[ a\%b = a - b(a/b) \]

我們可以得到：

\[bx+(a-b(a/b))y = \gcd(b,a\%b)=\gcd(a,b) \]

整理得到：

\[ ay + b(x-(a/b)y) = \gcd(a,b) \]

因此，我們令\(x'=y, y'=(x-(b/a)y)\)，就可以得到 \(ax'+by'=\gcd(a,b)\)了。
在程序中可以這樣簡寫：

inline ll exgcd(ll a, ll b, ll &x, ll &y)
{
    if(b == 0)
    {
	    x = 1, y = 0;
	    return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

一次同余方程FCE

一般形式為\(ax \equiv b \pmod{p}\)?？梢赞D換成\(ax + py = b\)的形式，然后用exgcd解出\((x,y)\)。
假設\(\gcd(a,p)\not \mid b\)，那么方程無解。
注意一下得到特解\(x_0\)后，方程的通解\(x \equiv x_0 \pmod{\frac{p}{\gcd(a,p)}}\)。

逆元

\(a\)在模\(p\)意義下的逆元為\(a^{-1}\)，則：\(a\cdot a^{-1} \equiv 1 \pmod{p}\)。這是一個FCE，直接求解就可以了。

值得注意的是逆元的幾種非常特殊的求法：

如果\(p\)是質數，那么\(a\)的逆元就是\(a^{p-2}\pmod{p}\)。
線性求逆元：\(i^{-1} \equiv (p-p/i)\times (p \% i)^{-1} \pmod{p}\)
線性求階乘逆元：\(\frac{1}{(i+1)!} \times (i+1) \equiv \frac{1}{i!} \pmod{p}\)

稍微注意一下，在用階乘求逆元時可能會出現\(p | i!\)的情況，此時階乘算出來都是\(0\)。

中國剩余定理

設方程組：

\[\begin{cases} x \equiv a_1 \pmod{p_1}\\ x \equiv a_2 \pmod{p_2}\\ \vdots\\ x \equiv a_k \pmod{p_k} \end{cases} \]

當\(p_1,p_2,\cdots,p_k\)兩兩互質時，設\(P=\prod_{i=1}^{k}p_i\)，則方程一定有整數解：

\[x \equiv \sum_{i = 1}^{k}a_i(\frac{P}{p_i})(\frac{P}{p_i})^{-1} \pmod{P} \]

其中\((\frac{P}{p_i})^{-1}(\frac{P}{p_i})\equiv 1 \pmod{p_i}\)。

假設\(p_1,p_2,\cdots,p_k\)不滿足兩兩互質，那么應該用擴展版本。

設\(x_{k-1}\)是通過EXCRT計算出的前\(k-1\)個方程的特解，而\(P_{k-1} = \prod_{i=1}^{k-1}p_i\)。為了讓它滿足第\(k\)個方程，有：

\[ x_{k-1} + \lambda P_{k-1} \equiv a_k \pmod{p_k} \]

已知\(x_{k-1},P_{k-1},a_k,p_k\)，這個方程就是一個關于\(\lambda\)的FCE，可以直接計算。當然，如果它無解，那整個方程組就都無解了。新的特解\(x_k=x_{k-1}+\lambda P_{k-1}\)通過加上或減去\(P_k\)就是前\(k\)個方程的特解。
另外有個小技巧：求乘積\(P_k\)可以改為求前\(k\)個模數的\(\operatorname{lcm}\)。粘貼核心代碼：

int main()
{
	n=qr(1);
	RP(i,1,n)
		m[i]=qr(1ll),a[i]=qr(1ll);//x = a[i] (mod m[i])
	
	ans=0,M=1;//M = prod
	RP(i,1,n)
	{
		ll p=FCE(M,a[i]-ans,m[i]);
		ans=ans+p*M;
		M*=m[i]/gcd(M,m[i]);
		ans=((ans%M)+M)%M;
	}
	printf("%lld",((ans%M)+M)%M);
	
	return 0;
}

高次同余方程（指數型）

求解形如\(a^{x}\equiv b \pmod{p}\)類型的，關于\(x\)的方程。其中有\(a,p\)互質，\(x\)非負。
這里沒有一般的解析方法。但是由于\(a,p\)互質，我們可以自由計算逆元，進行和\(a\)有關的乘除法。
設\(x = \epsilon t - \eta\)，其中\(t=\lceil\sqrt{p}\rceil\)，\(0\leq \eta < t\)。事先聲明，這樣的記法其實有點“混用”的意味，但事實上相比普通的拉丁字母，它更有助于記憶理解。
方程變成了：

\[ a^{\epsilon t - \eta}\equiv b \pmod{p} \]

即：

\[ a^{\epsilon t} \equiv b\cdot a^{\eta} \pmod{p} \]

對于所有的\(b\cdot a^{\eta},0 \leq \eta < t\)，我們將它插入一個Hash表中。枚舉\(\epsilon\)的所有取值\(0,1,\cdots,t\)，依次判斷在Hash表中是否有對應的\(b\cdot a^{\eta}\)，然后拼湊得到答案。
這種方法叫做Baby step，Giant step。是一種類分塊的優化枚舉。

簡單的線性代數

矩陣可以看成一個二維數表，可以用兩個緊挨的下標\(ij\)來標識位置\((i,j)\)處的元素。
矩陣加法就是對應的元素相加，即：\(C_{ij}=A_{ij}+B_{ij}\)。
矩陣乘法相對復雜。只有形如\(A_{(n\times k)}\)和\(B_{(k \times m)}\)才能相乘得到一個形如\(C_{(n\times m)}\)的矩陣。標準的公式：

\[ C_{ij}=\sum_{\lambda=1}^{k}A_{i\lambda}\cdot B_{\lambda j} \]

可以理解為：\(C_{ij}=A\)的第\(i\)行行向量\(\,\cdot\,B\)的第\(j\)列列向量。正所謂“行列式”，它說明行在前，列在后。

矩陣乘法的應用

對于一個\(k\)階的齊次線性遞推關系：

\[ x_n = a_1x_{n-1} + a_2x_{n-2} + \cdots+a_kx_{n-k} \]

由于是線性遞推關系，我們可以把所有的狀態\(x_n \sim x_{n-k}\)記錄下來，封裝到一個向量中去。即：

\[\begin{bmatrix} a_1 & a_2 & \cdots & a_{k-1} & a_k\\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 &0 \\ \vdots &\vdots & \cdots &\vdots &\vdots \\ 0 &0 & \cdots & 1 & 0 \end{bmatrix} \begin{bmatrix} x_n\\ x_{n-1}\\ x_{n-2}\\ \vdots\\ x_{n-k} \end{bmatrix}= \begin{bmatrix} x_{n+1}\\ x_{n}\\ x_{n-1}\\ \vdots\\ x_{n-k+1} \end{bmatrix} \]

此時這個\(k\)階方矩陣：

\[T = \begin{bmatrix} a_1 & a_2 & \cdots & a_{k-1} & a_k\\ 1 & 0 & \cdots & 0 & 0 \\ 0 & 1 & \cdots & 0 &0 \\ \vdots &\vdots & \cdots &\vdots &\vdots \\ 0 &0 & \cdots & 1 & 0 \end{bmatrix} \]

又叫作轉移矩陣。
如果知道這個遞推關系，想要從\(x_0,x_1,\cdots,x_k\)開始遞推\(c\)次，這個過程就等價于對這個列向量左乘\(c\)次，即\(T^c\)。由于矩陣乘法滿足結合律，這個過程可以用矩陣快速冪優化到\(O(k^3\log c)\)。
如果上面不是齊次遞推關系，而是帶了一個常數\(p\)（如\(a_n=2a_n+3\)），該怎么辦呢？可以直接把常數接在狀態向量的最下面，轉移矩陣賦值\(T_{k+1,k+1}=1\)，原封不動地轉移到新狀態去就可以了。
當然，直接代入矩陣乘法的公式，對著公式依次賦值，才是最穩妥的做法。

當然，矩陣乘法的應用不止于此?？紤]這樣一個問題：

給定一個帶邊權無向連通圖，求過\(k\)個點（不算起點），從\(1\)走到\(n\)的最短路？

設鄰接矩陣\(E_{ij}\)表示點\(i\)和\(j\)初始時的距離。如果兩點無邊相連，則賦值\(\infty\)。由于\(+\)和\(\times\)都具有交換律和結合律，而\(\min\)和\(+\)同樣具有交換律和結合律，我們可以把矩陣乘法\(\langle+,\times \rangle\)重定義成\(\langle \min, +\rangle\)。也就是說，每一次“乘法”：

\[ E'_{ij} = \min_{\lambda = 1}^{k}\{E_{i\lambda} + E_{\lambda j}\} \]

因此最終的答案就是\(E^{k}_{1,n}\)。可以用矩陣快速冪優化到\(O(n^3\log k)\)。

高斯消元

為節省空間，這里直接接一個鏈接過去。

線性基

狹義的線性基僅指異或空間下的線性基。其將大小為\(N\)的二進制集合，轉換為\(\log\)值域大小級別的集合，大大降低了時間和空間復雜度。但是線性基往往會破壞順序結構：你可以得到集合中若干數異或后的最大值，最小值，但卻無法具體得知你到底異或了哪些數。

線性基可以看成數表\(\{p_0,p_1,\cdots,p_k\}\)，其中\(p_i\)表示為\(1\)的最高位為\(i\)的數。它可能是由原來若干個數異或得到的。

當你想新插入一個數\(a\)到線性基中，你需要從高到低枚舉每一個已有的基底\(p_i\)。如果這個基底還沒有數插入，你當然可以選擇將這個位置加入\(a\)。但如果這一位上有數了，為了提高存儲效率，你需要令\(a = a \operatorname{xor} p_i\)從而消去這一位的值，然后繼續檢查低位的基底。

舉個例子。這個線性基：

\[ 100010\\ 010010\\ 000110\\ 000001\\ \]

就是一個不錯的線性基。而：

\[ 100010\\ 010010\\ 011100\\ 000110\\ 000101\\ \]

則非常糟糕。最高位為\(2,4\)的基底發生了重復，這兩對基底應該分別異或起來，再插入這個線性基中。
粘貼一下核心代碼：

void bits(ll x)
{
	DRP(i,62,0)
	{
		if(!(x >> (ll)i))
			continue;
		if(!p[i])
		{p[i] = x; break;}
		x ^= p[i];
	}
}
int main()
{
	scanf("%d", &n);
	RP(i,1,n)
		scanf("%lld", &a[i]), bits(a[i]);
	DRP(i,62,0)
		if((ans ^ p[i]) > ans)
			ans ^= p[i];
	cout<<ans;
	return 0;
}

posted @ 2019-09-23 16:52 LinearODE 閱讀(386) 評論(0) 收藏舉報

刷新頁面返回頂部

JasonZhou

且放白鹿青崖間