[算法] 数学问题

1. <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，后者还可以自定义比较函数

2. 模运算

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

• 大数求模
  (a*b) % c = (a % c * b % c) % c
  (a+b) % c = (a % c + b % c ) % c

3. 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)

4. 素数

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

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中期望意义上有个素数。
  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;
        }
    }
}

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

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的判断，因为最多只有一个大于的质因子

试除法求所有约数
大小为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)

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

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

8. 高精度

• 高精度加法

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;
}

• 高精度求模

9. 快速幂
   基于倍增的思想

求 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;
}

10. 求组合数
    Cnk mod p
11. 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;

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

乘法逆元

• 定义
  若整数b，m互质，并且b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为。
  逆元可以避免数论中除法产生非整数的情况
• 乘法逆元的特点
  
  乘法逆元的应用
  又根据 费马小定理
  
  可得b存在乘法逆元的充要条件是b与模数m互质且当模数m为质数时，即为b的乘法逆元；而如果m不是质数，则求逆元只能用扩展欧几里得定理

• 应用
  求组合数

  
  组合数阶乘

3. k <= 10^18 p是质数 Lucas定理

   
   

4. 欧拉函数
   欧拉函数 = 1到n中与n互质的n个数
   欧拉定理
   如果n是素数，
   如果n是合数，,
   

推广费马小定理
如果n是任一整数且a与n互素

12. 扩展欧几里得函数
    如果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

13. 高斯消元
    O(n^3)