math_牛客博客

等差数列

$a_{n} = a_{1} (n-1) d$

$s_{n} = \frac{n(a_{1} a_{n})}{2} = na_{1} \frac{n(n-1)}{2} d$

等比数列

$a_{n} = a_{1} q^{n-1}$

$s_n = \frac{a_{1} (1 - q^{n})}{1-q}$

乘法逆元

对于任意整数 $a$ 而言，如果 $a$ 和 $p$ 互质，存在一个整数 $x$ 使得 $a \times x \equiv 1(\bmod p)$

$x$ 为 $a$ 在模 $p$ 意义下的乘法逆元，记为 $a^{-1}$

不定方程 $ax by = 1$ 有解的充要条件是 $a,b$ 互质。

费马小定理: 若 $p$ 是质数，对任意整数 $a$ 不是 $p$ 的倍数，有 $a^{p-1} \equiv 1(\bmod p)$ ，也可以写作 $a^{p} \equiv$ $a(\bmod p)$ 。

证明: 根据同余的性质， $a, 2 a, 3 a \ldots \ldots,(p-1) a$ 分别 $\bmod p$ 的结果各不相同。那么:

\begin{aligned} a \times 2 a \times 3 a \ldots \ldots \times(p-1) a

如何求乘法逆元：若 $p$ 是质数，则有 $a^{p-1} \equiv 1(\bmod p)$ ，而 $a \times x \equiv 1(\bmod p)$ ，所以 $a^{p-2}$ 是 $a$ 模 $p$ 意义下的的乘法逆元。

可以用快速幂，时间复杂度为 $O(\log p)$

扩展欧几里得 $ax by = gcd(a,b)$

$gcd(a,b)$ = $ax by$

$gcd(b,a\%b)$ = $bx_{1} (a \% b) y_{1}$

= $bx_{1} (a - [a / b] * b)y_{1}$

= $ay_{1}$ + $b(x_{1} - [a/b]y_{1})$

$x = y_{1}$ , $y = x_{1} - [a/b]y_{1}$

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

若 $ax by = c$ ( $c$ 为 $gcd(a,b)$ 的倍数) 答案为 $x$ * $gcd(a,b)$

通解

$x = x_{0} \frac{b}{gcd(a,b)} * k$

$y = y_{0} - \frac{a}{gcd(a,b)} * k$

证明

$a(x n) b(y - m) = c$

$ax by an - bm = c$

$an - bm = 0 \\an = bm$

$\frac{a}{gcd(a,b)}*n = \frac{b}{gcd(a,b)} * m$

$a'n = b'm \\gcd(a',b') = 1 \\n = b' = b/gcd(a,b)\\ m = a' = a/gcd(a,b)$

递推求逆元

给定 $n,p$ ,求 1~ $n$ 在模 $p$ 意义下的逆元， $p$ 为质数

$inv[1] = 1;$

$inv[i] = (p - [p/i] * inv[p\%i]) \% p;$

阶乘逆元

给定 $n$ ,求 1~ $n$ 每个数阶乘在模 $p$ 意义下的逆元

$f(n-1)^{-1} = f(n)^{-1} * n$

算术基本定理

N = $p_{1}^{a_{1}} * p_{2} ^ {a_{2}}$ $\ldots$ $*p_{i} ^ {a_{i}}$ ( $p_{i}$ 为质数)

那么

N 的约数个数： $\sigma$ (N) = (1 + $a_{1}$ ) * (1 + $a_{2}$ ) * (1 + $a_{3}$ ) * $\ldots$ (1 + $a_{i}$ )

N 的各约数之和： $\mu$ (N) = (1 + $p_{1}^{1}$ + $p_{1}^{2}$ + $\ldots$ $p_{1}^{a1}$ ) * (1 + $p_{2}^{1}$ + $p_{2}^{2}$ ** + $\ldots$ $p_{2}^{a2}$ ) * $\ldots$ * (1 + $p_{i}^{1}$ + $p_{i}^{2}$ + $\ldots$ $p_{i}^{ai}$ ))

N ！ 进行算术基本定理的分解

找到 1~N 中质数
**每个质数的指数： ** $\frac{N}{prime[i] ^{1}}$ + $\frac{N}{prime[i]^{2}}$ + $\ldots$ 直至 N < $prime[i]^{m}$ ,除出结果为0

组合数取模

$C^{m}_{n}$ = $\frac{n!}{(n-m)!m!}$ **(乘法逆元取模 m <= n < $10^{5}$ ) 模为大质数费马小定理合数为exgcd **

** $C^{m}_{n}$ = ** $C^{m}_{n-1}$ + $C^{m-1}_{n-1}$ （预处理递推打标取模 m <= n < 2000）

Lucas 定理 $C^{m}_{n}$ % p = $C^{m/p}_{n/p}$ ***** $C^{m\%p }_{n\%p}$ $\%$ p (n , m < $10^{18}$ , (质数)p < $10^{5}$ )

 当 （n,m < p 时 ） return  C(n,m,p)

$C^{0}_{n}$ = 1;

$x^{2} \equiv 1(mod \ kn)$ $k \le n$

$1 \le n\le \ 200000000$

求 $x$ ,并从小到大输出

$O(logn)$ 筛质因子

$mindiv[]$ 表示一个数最小的质因子

能够在线性筛的过程中全部找出来 $mindiv$

#include <bits/stdc++.h>
using namespace std;
const int N = 2e6 + 50;
const int P = 10007;
typedef long long ll;
const int M = 2007;    
int n,m,k;
int plist[N];
int mindiv[N * 10];
bool not_prime[N * 10];
void init() {
    int T = 1e7;
    int cnt = 0;
    mindiv[1] = 1;
    for(int i = 2;i <= T; i ++) {
        if(not_prime[i] == false) {
            plist[++ cnt] = i;
            mindiv[i] = i;
        }
        for(int j = 1; j <= cnt; j ++) {
            int x = i * plist[j];
            if(x > T) break;
            not_prime[x] = true;
            mindiv[x] = plist[j];
            if(i % plist[j] == 0) break;
        }
    }
    return;
}
void solve() {
    scanf("%d",&n);
    while(n != 1) {
        int div = mindiv[n];
        if(mindiv[n] == div) {
            printf("%d ", div);
            while(mindiv[n] == div) {
                n /= div;
            }
        }
    }
    printf("\n");
    return;
}
int main() {
    int _ = 1;
    cin >> _;
    init();
    while(_ --) {
        solve();
    }
    return 0;
}