数学问题（四）

这部分内容介绍了同余，莫比乌斯函数性质，线性筛，计数初步
其中计数问题只涉及一些普通的模型

计数问题模型初步

隔板模型

组合数公式

• $${n \choose m} = {n \choose n-m}$$

• $${n \choose m} = {n-1 \choose m} + {n-1 \choose m-1}$$

  • proof
    对于第 $n$ 个元素，要么取，要么不取
    对应的在剩下的 $n-1$ 个元素中取 $m-1$ 个元素，或者是 $m$ 个元素

• $${n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n} = 2^n$$

  • proof
    每一个元素都有2种可能，取或者不取，一共是 $2^n$ 种可能
    另外，最后的方案数可能有 $0, 1, 2, \cdots, n$ 个元素
    根据加法原理，一共有 ${n \choose 0} + {n \choose 1} + {n \choose 2} + \cdots + {n \choose n}$ 种不同的方案

UVA10943

const int maxn = 200 + 10;
const int mod = 1e6;
int c[maxn][maxn];
int n, k;

void prework() {
    memset(c, 0, sizeof(c));
    _for(i, 1, maxn) {
        c[i][0] = c[i][i] = 1;
        _for(j, 1, i) {
            c[i][j] = (c[i-1][j-1] + c[i-1][j]) % mod;
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
    prework();
    while (scanf("%d%d", &n, &k) == 2 && n) {
        // init
        printf("%d\n", c[n+k-1][k-1]);
    }
}

重复元素的全排列

UVA11076

const int maxn = 15;
ll fac[maxn], num[maxn];

const ll one[13] = {0,1,11,111,1111,11111,111111,1111111,11111111,111111111,1111111111,11111111111,111111111111};
int n;

void init() {
    //
    memset(num, 0, sizeof(num));
}

void prework() {
    memset(fac, 0, sizeof(fac));
    fac[0] = 1, fac[1] = 1;

    for(int i = 2; i <= 12; i++) fac[i] = fac[i-1] * 1ll * i;
}

int main() {
    /*
    string str;
    for(int i = 1; i <= 12; i++) {
        str.clear();
        for(int t = 0; t < i; t++) str += '1';
        cout << str << ',';
    }
    */

    freopen("input.txt", "r", stdin);
    prework();

    while (scanf("%d", &n) == 1 && n) {
        init();

        ll sum = 0;
        _for(i, 0, n) {
            int x;
            scanf("%d", &x);
            sum += x;
            num[x]++;
        }

        ll ans = sum * fac[n-1];
        _rep(i, 0, 9) ans /= fac[num[i]];
        ans *= one[n];
        printf("%lld\n", ans);
    }
}

同余问题

同余类与最小剩余系

Euler-Fermat定理求解一次同余式
$(a,m)=1$，那么一次同余式

$$ax \equiv b (\bmod m)$$

的唯一解由

$$x \equiv ba^{\phi(m)-1} (\bmod m)$$

给出

HDU2462
$x$ 个 $8$ 连在一起组成的正整数可以写成

$$8 \times \frac{10^x - 1}{9}$$

求最小的 $x$，满足 $9L \mid 8(10^x - 1)$
$\textbf{let} \ d = \textbf{gcd}(L, 8)$

$$\Longrightarrow \frac{9L}{d} \mid (10^x -1) \Rightarrow 10^x \equiv 1 (\bmod \frac{9L}{d})$$

引理，若 $(a, n)=1$，则满足 $a^x \equiv 1 (\bmod n)$ 的最小正整数 $x_0$，满足
$x_0 \mid \phi(n)$
proof
反证法，不妨设 $\phi(n) = qx_0 + r \quad (0 < r < x_0)$
$a^{x_0} \equiv 1 (\bmod n) \Rightarrow a^{qx_0} \equiv 1(\bmod n)$
根据欧拉定理，有 $a^{\phi(n)} \equiv 1(\bmod n)$

$$\begin{cases} a^{qx_0} \equiv 1 (\bmod n) \\ a^{\phi(n)} \equiv 1 (\bmod n) \end{cases} \Rightarrow a^{r} \equiv 1(\bmod n) \Rightarrow r < x_0$$

矛盾

先重温一下快速幂

ll L;
const ll inf = 1e18;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

ll ksc(ll a, ll b, ll mod) {
    ll ans = 0;
    for(; b; b >>= 1) {
        if (b & 1) ans = (ans + a) % mod;
        a = (a * 2) % mod;
    }
    return ans;
}

ll ksm(ll a, ll b, ll mod) {
    ll ans = 1 % mod;
    a %= mod;

    for(; b; b >>= 1) {
        if (b & 1) ans = ksc(ans, a, mod);
        a = ksc(a, a, mod);
    }

    return ans;
}


ll phi(ll n) {
    ll ans = n;
    for(ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }

    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}

ll solve() {
    ll d = gcd(L, 8ll);
    ll mod = 9 * L / d;

    if (gcd(mod, 10ll) != 1) return 0;

    ll N = phi(mod);
    ll res = inf;

    for(ll i = 1; i <= sqrt(N); i++) {
        if (N % i) continue;
        if (ksm(10ll, i, mod) == 1) chmin(res, i);
        if (ksm(10ll, N/i, mod) == 1) chmin(res, N/i);
    }

    return res == inf ? 0 : res;
}

int main() {
    freopen("input.txt", "r", stdin);
    int kase = 0;
    while (cin >> L && L) {
        printf("Case %d: ", ++kase);

        ll res = solve();
        printf("%lld\n", res);
    }
}

扩展Euclid算法

Bezout定理
对于任意整数 $a, b$，存在一对整数 $x,y$，满足 $ax+by = \textbf{gcd}(a, b)$

根据数学归纳法做递归
$\textbf{i)} \ b = 0$，此时存在一对解 $x = 1, y = 0$
$\quad a\cdot 1 + 0 \cdot 0=\textbf{gcd}(a,0)=a$
$\textbf{ii)} \ b > 0$

$$\begin{cases} ax+by = \textbf{gcd}(a, b) && \textbf{gcd}(a, b) = \textbf{gcd}(b, a \bmod b) \\ bx + (a \bmod b) y = \textbf{gcd}(b, a \bmod b) \end{cases}$$

$$bx+(a \bmod b)y = bx+(a- \lfloor a/b \rfloor b) y = ay + b(x - \lfloor a/b\rfloor y)$$

$x' \leftarrow y$
$y' \leftarrow x - \lfloor a/b\rfloor y$
$ax'+by' = \textbf{gcd}(a, b)$

int exgcd(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }

    int d = exgcd(b, a % b, x, y);
    int z = x; x = y; y = z - (a/b) * y;
    return d;
}

对于一般方程 $ax+by = c$，可以先求出最大公约数 $(a, b) = d$
有解当且仅当 $d \mid c$

调用

exgcd(a, b, x0, y0)

求出方程的一组特解 $x_0, y_0$，原方程的一组特解就是

$$\frac{c}{d} \cdot x_0, \quad \frac{c}{d} \cdot y_0$$

通解是

$$x = \frac{c}{d} x_0 + k \frac{b}{d}, \quad y = \frac{c}{d} y_0 - k \frac{a}{d} \quad (k \in \mathbb{Z})$$

乘法逆元

$$a \cdot \frac{1}{b} \equiv a \cdot x (\bmod m)$$

其中 $b \mid a, \ \textbf{gcd}(b,m) = 1$

$x$ 是 $b$ 的 $\bmod m$ 乘法逆元
记为 $b^{-1} (\bmod m)$

$a/b \equiv a \cdot b^{-1} \equiv a/b \cdot b \cdot b^{-1} (\bmod m)$
$\Rightarrow b \cdot b^{-1} \equiv 1 (\bmod m)$

如果 $m$ 是素数，并且 $b < p$，有 $b^{p-1} \equiv 1 (\bmod p) \Leftrightarrow b \cdot b^{p-2} \equiv 1(\bmod m)$
$p$ 为质数的时候， $b^{p-2}$ 即为 $b$ 的乘法逆元

如果 $(b,m)=1$，乘法逆元可以通过求解线性同余方程得到
$b \cdot x \equiv 1 (\bmod m)$

乘法逆元在计算中的应用

$$\frac{a}{b} \Longrightarrow {a \leftarrow a \bmod p}, \ {b \leftarrow b \bmod p}$$

$a \cdot b^{-1} \bmod p$ 作为最终结果
当然前提是必须保证 $(b,p)=1$，也就是说 $b$ 不是 $p$ 的倍数

POJ1845

$$S_i = \frac{p_i^{B \cdot c_i + 1} - 1}{p_i - 1}$$

$A^B = \prod_{i \in [1,n]} S_i, M = 9901$

$\textbf{algorithm}$

• $(p_i^{B \cdot c_i + 1} - 1 ) \bmod M, \quad (p_i - 1) \bmod M$

• 如果 $p_i - 1$ 不是 $M$ 的倍数，那么这个数的乘法逆元
  $inv = (p_i - 1)^{M-2}$，用 $\times inv$ 代替除法

  如果 $p_i - 1 = kM$，那么 $p_i \equiv 1 (\bmod M)$
  $1 + p_i + p_i^{2} + \cdots + p_i^{B\cdot c_i} \equiv 1 + 1+ \cdots \equiv B \cdot c_i + 1(\bmod M)$

const int mod = 9901;
ll a, b;

class A {
public:
    int p, c;
    A() = default;
    A(int p) : p(p) {
        c = 0;
    }
};

vector<A> P;

void divide(ll n) {
    P.clear();
    for(ll i = 2; i * i <= n; i++) {
        if (n % i == 0) {
            P.push_back(A(i));
            while (n % i == 0) n /= i, P.back().c++;
        }
    }
    if (n > 1) P.push_back(n), P.back().c = 1;
}

void solve() {
    ll ans = 1;
    divide(a);

    _for(i, 0, P.size()) {
        if ((P[i].p - 1) % mod == 0) {
            ans = (b * P[i].c + 1) % mod * ans % mod;
            continue;
        }

        ll x = ksm(P[i].p, b*P[i].c+1, mod);
        x = (x - 1 + mod) % mod;

        ll y = P[i].p - 1;
        y = ksm(y, mod - 2, mod);
        ans = ans * x % mod * y % mod;
    }

    cout << ans << endl;
}

void init() {
    //
}

int main() {
    freopen("input.txt", "r", stdin);
    cin >> a >> b;
    init();

    // then solve
    solve();
}