[算法] 数学问题

2019-01-19 本文已影响0人舒也ella

<cmath>中常用函数
pow(base, exponent)
sqrt(x)
fmax、fmin、fabs
ceil、floor、round（四舍五入）
上述这些返回值和参数默认都是浮点数 注意强制类型转换注意double强制转int 向下舍入
e.x. %的除数和被除数都必须为整型变量且除数不能为0否则runtime error
abs的返回值虽然是整型，但它同时为整型和浮点型重载，可替代fabs
fmin、fmax是<cmath>中求最值的方法，不过我们通常使用algorithm头文件中的min 、max，后者还可以自定义比较函数
模运算

负数取模
e.x. 日期与当前日期的天数差值可能为负
(days % 7 + 7) % 7
加上求模的除数仍要再取一次模，保证原来模为0的情况仍为0
大数求模
(a*b) % c = (a % c * b % c) % c
(a+b) % c = (a % c + b % c ) % c

GCD & LCM
最大公约数 Greatest Common Divisor
欧几里得算法辗转相除

while( b!= 0) {
int t = a % b;
a = b;
b = t;
}
return a;
// 一行
int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

最小公倍数 Least Common Multiple
a * b / gcd(a,b)

素数

试除法素数判定
因子必定是成对出现的

bool is_prime(int x)
{
    if (x < 2) return false;
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
            return false;
    return true;
}

素数筛法
1到n中期望意义上有 $n/ \ln n$ 个素数。
Sieve of Eratosthenes 排除法
O(n*log(log(n)))

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉
void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (st[i]) continue;
        primes[cnt ++ ] = i;
        for (int j = i; j <= n; j += i)
            st[j] = true;
    }
}

Sieve of Euler 欧拉筛法
O(n) 每个数只被它最小的质因子筛掉

int primes[N], cnt;     // primes[]存储所有素数
bool st[N];         // st[x]存储x是否被筛掉

void get_primes(int n)
{
    for (int i = 2; i <= n; i ++ )
    {
        if (!st[i]) primes[cnt ++ ] = i;
        for (int j = 0; primes[j] <= n / i; j ++ )
        {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

分解质因数
试除法分解质因数

void divide(int x)
{
    for (int i = 2; i <= x / i; i ++ )
        if (x % i == 0)
        {
            int s = 0;
            while (x % i == 0) x /= i, s ++ ;
            cout << i << ' ' << s << endl;
        }
    if (x > 1) cout << x << ' ' << 1 << endl;
    cout << endl;
}

最后要多加一步x>1的判断，因为最多只有一个大于 $\sqrt n$ 的质因子

试除法求所有约数
大小为a的数的期望的约数个数为 $\ln a$ 个

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

如果 N = p1^c1 * p2^c2 * ... *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * ... * (ck + 1)
约数之和： (p1^0 + p1^1 + ... + p1^c1) * ... * (pk^0 + pk^1 + ... + pk^ck)
求解幂次求和
普通做法O(n)
分治O(lgn)

数位拆解
do{
} while(a != 0);
可避免数本身为0时未分解到任何结果的情况
进制转换

注意字符与数字比较时一定记得加单引号'0'
注意向字符串转换和从字符串转换时的反序和反向遍历操作
注意处理0和负数
从字符串转换时判断s[0] == '-' ，向字符串转换时0和负数的构造

高精度

高精度加法

vector<int> bigAdd(vector<int>& a, vector<int>& b) {
    vector<int> res;
    int alen = (int)a.size();
    int blen = (int)b.size();
    for (int i = 0, g = 0; ; i++) {
        if (g == 0 && i >= alen && i > blen) {
            break;
        }
        if (i < alen) {
            g += a[i];
        }
        if (i < blen) {
            g += b[i];
        }
        res.push_back(g % BASE);
        g /= BASE;
    }
    return res;
}

高精度乘法

vector<int> bigMul(vector<int>& a, vector<int>& b) {
    int alen = (int)a.size();
    int blen = (int)b.size();
    int index;
    for (index = 0; index < a.size() && a[index] == 0; index++) {}
    if (index == a.size()) return { 0 };
    for (index = 0; index < b.size() && b[index] == 0; index++) {}
    if (index == b.size()) return { 0 };
    vector<int> res(alen + blen, 0);
    // i*j存放i+j
    for (int i = 0; i < alen; i++) {
        for (int j = 0; j < blen; j++) {
            res[i + j] += a[i] * b[j];
        }
    }
    int g = 0;
    for (int i = 0; i < (int)res.size(); i++) {
        int tmp = res[i] + g;
        res[i] = tmp % BASE;
        g = tmp / BASE;
    }
    while (res.back() == 0) {
        res.pop_back();
    }
    return res;
}

高精度求模

快速幂
基于倍增的思想

求 m^k mod p，时间复杂度 O(logk)。
int qmi(int m, int k, int p)
{
    int res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = res * t % p;
        t = t * t % p;
        k >>= 1;
    }
    return res;
}

矩阵快速幂

mat qPow (mat A, ll n) {
    int len = (int)A.size();
    mat res(len, vector<BigInt>(len));
    res[0][0] = res[1][1] = 1;
    res[0][1] = res[1][0] = 0;
    while (n) {
        if ( n & 1 ) {
            res = matrixMultiply(res, A);
        }
        A = matrixMultiply(A, A);
        n >>= 1;
    }
    return res;
}

求组合数
Cnk mod p
k <= 2000 递推法

// c[a][b] 表示从a个苹果中选b个的方案数
for (int i = 0; i < N; i ++ )
    for (int j = 0; j <= i; j ++ )
        if (!j) c[i][j] = 1;
        else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;

k <= 10^5 逆元法预处理

乘法逆元

定义
若整数b，m互质，并且b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为 $b^{−1} (mod \; m)$ 。
逆元可以避免数论中除法产生非整数的情况

乘法逆元的特点
$bb^{-1} ≡ 1 (mod \; m)$
乘法逆元的应用
又根据费马小定理
$b^{p-1} ≡ 1 (mod \; p)$
可得b存在乘法逆元的充要条件是b与模数m互质且当模数m为质数时， $b^{m−2}$ 即为b的乘法逆元；而如果m不是质数，则求逆元只能用扩展欧几里得定理

应用
求组合数

组合数阶乘

k <= 10^18 p是质数 Lucas定理
欧拉函数
欧拉函数 $\phi(n)$ = 1到n中与n互质的n个数
欧拉定理
如果n是素数， $\phi(n) = p - 1$
如果n是合数， $n = p_1^{a_1}p_2^{a_2}...p_r^{a_r}$ ,
$\phi(n) = n(1- 1/p_1)(1- 1/p_2)...(1- 1/p_r)$

推广费马小定理
如果n是任一整数且a与n互素
$a^{\phi(n)} ≡ 1 (mod \; m)$

扩展欧几里得函数
如果d|a且d|b，则d|(a+b), d|(qa + pb)

裴蜀定理
有任意正整数a, b，gcd（a，b）=d，那么对于任意的整数x，y，ax+by都一定是d的倍数，特别地，一定存在整数x，y，使ax+by=d成立。
推论
a,b互素的充要条件是存在整数x，y使ax+by=1

高斯消元
O(n^3)

[算法] 数学问题

猜你喜欢

热点阅读