Bzoj 1016
先看定理(转自discuss, 证明看原文)：
定理一：如果 $A, B$ 同为 $G$ 的最小生成树，且 $A$ 的边权从小到大为 $w(a_1), w(a_2), w(a_3), \cdots w(a_n)$，$B$ 的边权从小到大为 $w(b_1), w(b_2), w(b_3), \cdots w(b_n)$，则有 $w(a_i) = w(b_i)$。
定理二：如果 $A, B$ 同为 $G$ 的最小生成树，如果 $A, B$ 都从零开始从小到大加边（$A$ 加 $A$ 的边，$B$ 加 $B$ 的边）的话，每种权值加完后图的联通性相同。
定理三：如果在最小生成树 $A$ 中权值为 $v$ 的边有 $k$ 条，用任意 $k$ 条权值为 $v$ 的边替换 $A$ 中的权为 $v$ 的边且不产生环的方案都是一棵合法最小生成树。

那么这题我们先做一次最小生成树，然后统计各种权值用的边数(用权值分组)，然后每组再dfs找出相应边数的边使得每一条边都可以使图的连通分量减少。然后每组的方案再乘法原理求。一个组的搜完了，还要把这个权值的边都连上，再搜下一次。

注意这时并查集不要路径压缩，因为dfs要回溯，此时并查集复杂度为$O(nlogn)$。
还有图不连通的情况，这种情况不存在最小生成树，然后注意这题还要取模

阅读全文 »

模板及讲解

数论常用方法

1、$a\% b = a-\lfloor \frac ab \rfloor\cdot b$
2、设$p=ki+r$，$k=\lfloor \frac pi \rfloor, r = p \mod i$
3、$a|c \Leftrightarrow a \equiv 0 \pmod c \Leftrightarrow c \% a = 0 \Leftrightarrow c = ka$
4、设出最小素因子

积性函数

积性函数：对于正整数$n$的一个算术函数$f(n)$，若$f(1)=1$，且当$a,b$互质时$f(ab)=f(a)f(b)$。
完全积性函数：所有对于任何$a,b$都有性质$f(ab)=f(a)f(b)$的函数。

积性函数有：$\varphi(n), \mu(n),d(n),\gcd(n,k),\sigma(n)$ 等

性质：
1、若$n=p_{1}^{a_{1}}p_{2}^{a_{2}}p_{3}^{a_{3}}…p_{n}^{a_{n}}$, 则$f(n)=f(p_{1}^{a_{1}})f(p_{2}^{a_{2}})f(p_{3}^{a_{3}})…f(p_{n}^{a_{n}})$
2、若$f$为积性函数且$f(p^{n})=f^{n}(p)$，则$f$为完全积性函数

积性函数可以由线性筛$O(n)$筛出。

欧几里得算法

求$\gcd(a, b)$，即$a$和$b$的最大公倍数

欧几里得算法：

$$\gcd(a, b) = \gcd(b, a \% b)$$

int gcd(int a, int b) {
    if (b == 0) return a;
    gcd(b, a % b);
}

性质：

1、$\gcd(a,b)=c$则$a=k_1c, b=k_2c \Leftrightarrow c | a, c | b, c|(a +b)$
2、$ab/ \gcd(a,b)=\operatorname{lcm}(a,b)$
3、$\gcd(a,b)=\gcd(a+bp,b), p \in N$
4、$a,b$互质$\Leftrightarrow \gcd(a,b)=1 \Leftrightarrow \exists x, ax+by=1$
5、对于两个正整数$a,b$设$\gcd(a,b)=k$则存在$\gcd(\frac ak, \frac bk)=1$。推论$m\cdot \gcd(a, b)=\gcd(ma, mb)$
6、设$b | ac, \gcd(b, c)= 1$，则$b|a$
7、更相减损法：$\gcd(a,b)=\gcd(a, a-b)=\gcd(b, a-b) , a \leq b$
8、因为$\gcd(n, x)=\gcd(n, n - x)$，所以如果$x, n$互质，则$n-x, n$互质，即与$n$互质的数成对出现

引理：

当所有数不全部相同时，$\gcd\left ( i_1, i_2, \dots, i_N \right ) \leq \max\left ( i_1, i_2, \dots, i_N \right ) - \min\left ( i_1, i_2, \dots, i_N \right )$

证明：设$d = \gcd\left ( i_1, i_2, \dots, i_N \right ), a = \min\left ( i_1, i_2, \dots, i_N \right ), b = \max\left ( i_1, i_2, \dots, i_N \right )$
显然$a = k_1d (k_1 \in \mathbb{Z}^+), b = k_2d (k_2 \in \mathbb{Z}^+, k_2 > k_1)$，所以$b - a \geq d$，证毕。

扩展欧几里得算法

求$ax+by=\gcd(a,b)$的解$x,y$

已求出下一个状态一组解$x1,y1$使得$b\cdot x1+(a\% b) \cdot y1=\gcd(a,b)$
由$a\%b=a-\lfloor \frac ab \rfloor\cdot b$,得
$b \cdot x1 +(a-\lfloor \frac ab \rfloor\cdot b) \cdot y1 = \gcd(a,b)$
$b \cdot x1 + a \cdot y1 - b \cdot y1 \cdot \lfloor \frac ab \rfloor = \gcd(a,b)$
$a \cdot y1 + b\cdot (x1-y1\cdot \lfloor \frac ab \rfloor)= \gcd(a,b)$
对照$ax+by=\gcd(a,b)$，可得
$x = y1, y= x1-y1\cdot \lfloor \frac ab\rfloor$
由欧几里得算法终止条件$a=\gcd(a,b), b=0$得，$a \times 1+b \times 0=\gcd(a,b)$
所以$x,y$的边界值是$1，0$

通解：
$$
x = x_1 + \frac {b}{\gcd(a,b)} \cdot n\\
y = y_1 – \frac {a}{\gcd(a,b)} \cdot n
$$
证明：

在原有方程左右两侧同除一个$g=\gcd(a,b)$, 得$x \cdot \frac{a}{g}+y \cdot \frac{b}{g}=1$
$x \cdot \frac{a}{g} + \frac{ab}{g^2} +y \cdot \frac{b}{g} - \frac{ab}{g^2} =1$
合并同类项，$\frac ag(x+\frac bg) + \frac bg (y - \frac ag)=1$
所以$(x+\frac bg, y-\frac ag), (x+2\cdot\frac bg, y-2 \cdot \frac ag)$都是原不定方程的解，这个方程的解具有周期性
由此可得$x$的周期为$b/g$, $y$的周期为$a/g$，得出通解

int exgcd(int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1, y = 0;//边界值
        return a;//求最大公倍数
    }
    int ans = exgcd(b, a % b, x, y);
    int tmp = x;
    x = y;
    y = tmp - y * a / b;//公式计算
    return ans;
}

(3) 求不定方程$ax+by=c$的最小一组解$x,y$, (Bzoj 1477)

先求出$g = \gcd(a,b)$
如果$c\%g≠0$,无解
否则，将不定方程两边同时除以$g$，得$a_1x+b_1y=c_1$
此时$\gcd(a_1,b_1)=1$,可用扩展欧几里得算法求出$a_1x_1+b_1y_1=1$的解$x_1,y_1$
即$a_1x+b_1y=c_1$的一组解为$x1\cdot c1, y1\cdot c1$
求最小解可用一组特解模$b/\gcd(a, b)$即可得到(由通解周期性可以得知)

(4) 求$a $关于$ n $的乘法逆元, NOIP2012 D2 T1

$(a / b) \% k = (a \cdot b^{-1}) \% k$，$b^{-1}$是$b$的乘法逆元，只有 $ a, k$ 互质($\gcd(a,k)=1$)，才有逆元

$ax\equiv 1\pmod n$
由同余性质得，$ax-1=ny$
变形，得 $ax-ny=1$，此时$\gcd(a,n)$必须为$1$且只有唯一解, 否则无解
即可使用扩展欧几里得算法求解，最后使解在$[0, n-1]$之间
求最小解可用一组特解模$n/\gcd(a, n)=n$(此时$\gcd(a, n)=1$, 否则无解)即可得到(由通解周期性可以得知)

同余

设$m$为正整数，$a,b$是整数，如果$(a \mod m) =(b \mod m)$(或者$a-b$是$m$的整数倍)，那么就说$a$和$b$关于$m$同余。

(1) 同余定理: 如果$a\equiv b\pmod m$，那么$(a - b) = my(y$是常数，且为整数)
(2) $a\equiv a\pmod m$
(3) 如果$a\equiv b\pmod m$，那么$b\equiv a\pmod m$
(4) 如果$a\equiv b\pmod m, b\equiv c\pmod m$，那么$a\equiv c\pmod m$

中国剩余定理

设正整数$m_1,m_2,…,m_k$两两互素，则同余方程组
$$
\begin{cases}
x&\equiv&a_1&\pmod{m_1}\\
x&\equiv&a_2&\pmod{m_2}\\
&&&\vdots\\
x&\equiv&a_k&\pmod {m_k}
\end{cases}
$$
有整数解。并且在模$M = m_1 \cdot m_2 \cdot …\cdot mk$下有唯一解，
解为
$$x \equiv (a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+…+a_kM_kM_k^{-1}) \pmod M$$
其中$M_i= \frac M{m_i}，M_i^{-1}$是$M_i$模$m_i$下的逆元

解法：先$O(n)$的时间求出$M$，然后求出$M_i$, 用扩展欧几里得算法求出$M_i^{-1}$，根据公式进行计算

证明：

我们先考虑只求出满足一个方程的解$x_i$，其他$a_i$都为$0$, 如下(使这个$x$只在这一维中有余数)
$$
\begin{cases}
x&\equiv&0&\pmod{m_1}\\
x&\equiv&0&\pmod{m_2}\\
&&&\vdots\\
x&\equiv&a_i&\pmod {m_i}\\
&&&\vdots\\
x&\equiv&0&\pmod {m_k}
\end{cases}
$$
这样有些困难，我们先求
$$
\begin{cases}
x&\equiv&0&\pmod{m_1}\\
x&\equiv&0&\pmod{m_2}\\
&&&\vdots\\
x&\equiv&1&\pmod {m_i}\\
&&&\vdots\\
x&\equiv&0&\pmod {m_k}
\end{cases}
$$
然后再乘回$a_i$就能得到前面的解了，现在来解$x \equiv 1 \pmod {m_i}$
设$M=m_1 \cdot m_2 \cdot …\cdot mk, M_i= \frac M{m_i}$，显然$Mi|x$，所以我们可以设$x=yMi$
那么$x \equiv 1 \pmod {m_i} \Leftrightarrow yMi \equiv 1 \pmod {m_i}$
注意到这里$y$为$Mi$在模$m_i$的意义下的逆元，即$y=Mi^{-1}$，那么$x=MiMi^{-1}$

那么这个方程组的一个方程的解就算出来了，我们算前面的方程组的那个方程的解，为$x=a_iMiMi^{-1}$
由于这个只能满足一个方程，所以我们要把所有的方程解都算出来求和即可，然后模$M$就能得到最终解，即$x \equiv (a_1M_1M_1^{-1}+a_2M_2M_2^{-1}+…+a_kM_kM_k^{-1}) \pmod M$

Poj 1006

int crt(int n, int *a, int *m) {
    int ans = 0;
    int M = 1;
    for (int i = 1; i <= n; i++) M *= m[i];
    for (int i = 1; i <= n; i++) {
        int Mi = M / m[i];
        int x, y;
        e_gcd(Mi, m[i], x, y);//求Mi的逆元x
        ans = (ans + a[i] * Mi * x) % M;
    }
    return (ans + M) % M;
}

扩展中国剩余定理

对于正整数$m_1,m_2,…,m_k$不满足两两互素，那就需要每个方程两两合并。合并过程如下

$$
\begin{cases}
x&\equiv&a_1&\pmod{m_1}(1)\\
x&\equiv&a_2&\pmod{m_2}(2)\\
&&&\vdots\\
x&\equiv&a_k&\pmod {m_k}
\end{cases}
$$
由(1)(2)，得
$x=a_1+m_1x_1(3)$
$x=a_2+m_2x_2(4)$
联立，$a_1+m_1x_1=a_2+m_2x_2$
移项，$m_1x_1+m_2x_2=a_2-a_1$
用exgcd判是否有解并解出一个特解$x_0$(只要$x_0$不要$y_0$)
将$x_0$带入(3), 得$x=a_1+m_1x_0$
用通解表示为(其中$g=\gcd(m_1, m_2)$)
$x=a_1+m_1(x_0+\frac{m_2}{g} \cdot n)=m_1x_0+a_1+n \cdot \frac{m_1m_2}{g}$
因为$\operatorname{lcm}(a1, a2)=\frac{m_1m_2}{g}$, 所以得到
$x \equiv (m_1x_0+a_1) \pmod{\operatorname{lcm}(m1, m2)}$
用这个方程继续和下面的方程合并即可

Hdu 3579

求正约数的个数/正约数和

给出n的唯一分解式 $n = p^{a1}_1p^{a2}_2p^{a3}_3…p^{ak}_k$ , 求出 $n$ 的正约数的个数，并且求出正约数和
根据乘法原理，$n$ 的正约数的个数为
$$\prod_{i=1}^{k}(a_i+1)$$

正约数个数的前缀和$\sum_{i=1}^{n} \lfloor \frac ni \rfloor ≈ n\sum_{i=1}^{n} \frac 1i ≈ n(lnn+\gamma )$

根据乘法原理，$n$ 的正约数和为
$$\prod_{i=1}^{k}(\sum_{j=0}^{a_i} p_i^j)$$

线性筛

线性筛可以筛出积性函数。

欧拉筛求质数

时间复杂度 $O(n\log(\log n))$，大约能跑$n=10^7$的数据

int vis[n];
int sx() {
    int m = sqrt(n + 0.5);
    ms(vis,0);
    for (int i = 2; i <= n; i++)
    if (!vis[i]) for (int j = i * i; j <= n; j += i) vis[j] = 1;
}

线性筛质数

Luogu 3383

考虑每个合数被它的最小素因子筛去，所以枚举的每个$i$之后枚举质数来筛去对应合数，并且如果$pri|i$就要break了，这样做到不重不漏。
时间复杂度 $O(n)$

vis[1] = 1;
for (int i = 2; i <= n; ++i) {
    if (!vis[i]) pri[++tot] = i;
    for (int j = 1; j <= tot && (LL)i * (LL)pri[j] <= (LL)n; ++j) {
        vis[i * pri[j]] = 1;
        if (i % pri[j] == 0) break;
    }
}

线性筛因数个数函数 $d_0(n)$

$d_k(n)$表示$n$因数$k$次方的和。
$d_0(n)$即为因数个数

我们筛选需要$3$个数组，$pri(i)$当前质数数组，$d(i)$因数个数函数，$e(i)$最小质因子个数。
由$n=\prod_{i=1}^{k}(a_i+1)$，我们可以用这个正约数公式来筛选。

对于当前枚举的$i, pri$ ，$pri$不超过$i$, 我们用$pri \cdot i$来顶掉$pri \cdot i$使其不会成为质数。$e(pri \cdot i)=1$为$pri$.
当前数是素数，则$d(i)=2, e(i)=1$
如果$pri\nmid i$，由于$pri$为质数所以$pri,i$互质，利用积性函数性质：$d(i \cdot pri)=d(i)d(pri)=2d(i), e(pri \cdot i)=1$
如果$pri\mid i$，由于$d(i)=\prod_{i=1}^{k}(a_i+1)$，其中$e_i=pri$，所以要把$(a_1+1)$除掉之后再乘上$(a_1+2)$，即$d(i \cdot pri)=d(i)/(e(i)+1)\cdot (e(i)+2)$，显然此时$e(pri \cdot i)=e(i)+1$

线性筛因数和函数 $d_1(n)$

$d_k(n)$表示$n$因数$k$次方的和。
$d_1(n)$即为因数和
运用公式和前因数个数面的推导，不难写出以下程序

vis[1] = 1, d[0] = 0, d[1] = 1;
for (LL i = 2; i <= MAX_N; i++) {
    if (!vis[i]) pri[++tot] = i, e[i] = i + 1, d[i] = i + 1;
        for (LL j = 1; j <= tot && pri[j] * i <= MAX_N; j++) {
        vis[pri[j] * i] = 1;
        if (i % pri[j] == 0) {
            d[pri[j] * i] = d[i] / e[i] * (e[i] * pri[j] + 1);
            e[pri[j] * i] = e[i] * pri[j] + 1;
            break;
        } else d[pri[j] * i] = d[pri[j]] * d[i], e[pri[j] * i] = 1 + pri[j];
    }
}

分解质因数

给出$n$，求出$n=A^{B_1}_1 \times A^{B_2}_2 \times … \times A^{B_k}_k$的$A_i$及$B_i$($A_i$为质数)
从1到$\sqrt n$进行找$n$的因子，找到就除干净，注意最后可能$n$还会大于1，特判即可
$\sqrt n$判断可以是$i^2 \leq x$，$x$是当前的$n$

for (LL i = 2; i * i <= x; i++) {
    if (x % i == 0) {
        //i 是质因数
        while (x % i == 0) x /= i;
    }
}
if (x != 1) //x 是质因数

阅读全文 »

「Bzoj 1016」「JSOI2008」最小生成树计数 (最小生成树+乘法原理)

「Bzoj 1015」「JSOI2008」星球大战starwar (并查集+离线逆向思维)

「Bzoj 1087」「SCOI2005」互不侵犯King (状压DP)

「Bzoj 1076」「SCOI2008」奖励关 (状压概率期望DP)

「Bzoj 1821」「JSOI2010」部落划分 Group (最小生成树)

Bzoj 3109(DFS)

「Bzoj 1295」「SCOI2009」最长距离 (最短路)

「Bzoj 1096」「ZJOI2007」仓库建设 (斜率优化DP)

「Bzoj 1477」青蛙的约会 (扩展欧几里得算法解不定方程)

数论基础学习笔记