数学总结

这个暑假是把数学好好补了补，原来就和小白一样（虽然现在也是）

质数

·质数的判定(O(sqrt n))

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

·欧拉筛质数(O(nlog n))

int ban[MAXN];
for(int i = 2; i <= n; ++i)
   for(int j = 2; i * j <= n; ++j)
      ban[i * j] = 1;
}

·线性筛质数(O(n))

int v[MAXN], prime[MAXN], cnt, is[MAXN];
for(int i = 2; i <= n; ++i)
   if(!v[i]){
      v[i] = i;
      prime[++cnt] = i;
      is[i] = 1;
   }
   for(int j = 1; j <= cnt; ++j){
      if(v[i] < prime[j] || prime[j] > n / i) break;
        v[i * prime[j]] = prime[j];
   }
}

约数

·唯一分解定理：任意数(n)可表示为(p_1^{c_1}*p_2^{c_2}*...*p_m^{c_m})
·质因数分解(O(sqrt n))
·约数个数(num=prod_{i=1}^{m}(c_i+1))
·约数和(sum=prod_{i=1}^{m}(sum_{j=0}^{c_i}p_i^j))

最大公约数

·欧几里得算法 (O(log{max(a,b))})

int gcd(int a, int b){
    return !b ? a : gcd(b, a%b);
}

·更相减损术 (O(log{max(a,b))})(加优化后)

int gcd(int a, int b){
    if(a % b == 0) return b;
    if(b % a == 0) return a;
    if(a % 2 && !(b % 2)) return gcd(a, b / 2);
    if(!(a % 2) && b % 2) return gcd(a / 2, b);
    if(!(a % 2) && !(b % 2)) return gcd(a / 2, b / 2) * 2;
    if(b > a) swap(a, b);
    return gcd(b, a - b);
}

欧拉函数

·定义：(phi(n))=小于等于n的与n互质的数的个数
·欧拉函数为积性函数
·求欧拉函数(O(sqrt n))：(phi(n)=n*prod_{ ext{质数}p|n}(1-frac{1}{p}))
·线性筛欧拉函数(O(n))

//线性筛欧拉
for(int i = 2; i <= n; ++i){
       if(!v[i]){
         v[i] = i;
         prime[++cnt] = i;
         phi[i] = i - 1;
       }
       for(int j = 1; j <= cnt; ++j){
          if(prime[j] > n / i) break;
          v[prime[j] * i] = prime[j];
          if(i % prime[j] == 0){
            phi[prime[j] * i] = phi[i] * prime[j];
            break;
          }
          else phi[prime[j] * i] = phi[i] * (prime[j] - 1);
       }
    }

同余

·费马小定理：若(p)是质数，则有(a^pequiv apmod p)
·欧拉定理：若(a,n)互质，则有(a^{phi(n)}equiv1pmod n)
·欧拉定理推论：若(a,n)互质，则有(a^bequiv a^{b mod phi(n)}pmod n)
·扩展欧几里得算法：在(O(log{max(a,b))})的时间复杂度内得出方程(ax+by=gcd(a,b))的一组解

int exgcd(int a, int b, int &x, int &y){
    if(!b){  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;
}

逆元

·定义：若(axequiv1pmod n)，则(x)为(a)在模(n)意义下的逆元，记为(a^{-1})

求逆元

·扩展欧几里得算法：(exgcd(a,n,x,y) ext{得到的}x即为逆元)
·若(n)为质数，可用费马小定理的变式：(x=a^{n-2})
·线性递推(1)~(n)模(p)意义下的逆元：(inv[i]=(p-leftlfloorfrac{p}{i} ight floor)*inv[pmod i]mod p)(边界：(inv[1]=1))

中国剩余定理

若(m_1,m_2,...,m_n)是两两互质的正整数，则同余方程组

[egin{cases}xequiv a_1pmod{m_1}\xequiv a_2pmod{m_2}\xequiv a_3pmod{m_3}\...\xequiv a_npmod{m_n}\end{cases} ]

有整数解，解为(x=sum_{i=1}^na_iM_it_i)，
其中，(M_i)为(frac{m}{a_i})。
其中(m=sum_{i=1}^nm_i)，
(t_i)为线性同余方程(M_it_iequiv 1pmod{m_i})的一个解。

//洛谷P3868 猜数字
#include <cstdio>
const int MAXN = 15;
typedef long long ll;
ll a[MAXN], b[MAXN], M[MAXN], tot = 1, ans, x, y;
int n;
void exgcd(ll a, ll b, ll &x, ll &y){
    if(!b){
      x = 1; y = 0;
    }
    else{
      exgcd(b, a % b, x, y);
      ll z = x; x = y; y = z - (a / b) * y;
    }
}
ll Slow_Mul(ll n, ll k, ll mod){
    ll ans = 0;
    while(k){
      if(k & 1) ans = (ans + n) % mod;
      k >>= 1;
      n = (n + n) % mod;
    }
    return ans;
}
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
       scanf("%lld", &a[i]);
    for(int i = 1; i <= n; ++i)
       scanf("%lld", &b[i]), tot *= b[i];
    for(int i = 1; i <= n; ++i){
       M[i] = tot / b[i];
       exgcd(M[i], b[i], x, y);
       ans = (ans + Slow_Mul(Slow_Mul(a[i], M[i], tot), ((x % tot) + tot) % tot, tot)) % tot;
    }
    printf("%lld
", ans);
    return 0;
}

扩展中国剩余定理（EXCRT）

见这里

高次同余方程

·问题：(a,p)互质，求一个非负整数(x)，使得(a^xequiv bpmod p)
·(BSGS)算法
设$$a^{i*t-j}equiv bpmod p$$，其中(t=leftlceilsqrt p ight ceil)。

式子两边同乘(a^j)得$$a^{it}equiv ba^jpmod p$$于是就可以枚举所有(j[0,t))，把所有(b*a^j)的值存入一个(Hash)表，然后再枚举(i[0,t])，算出((a^i)^tmod p)，看(Hash)表里有没有对应的值，如果有，那么答案就是(i*t-j)了。

int BSGS(int a, int b, int p){   //a^x≡b(mod p)
    map <int, int> hash; hash.clear();
    int t = ceil(sqrt(p));
    for(int i = 0; i < t; ++i){
       int val = (long long)b * fast_pow(a, i, p) % p;
       hash[val] = i;
    }
    a = fast_pow(a, t, p);
    if(!a) return !b ? 1 : -1;
    for(int i = 0; i <= t; ++i){
       int j = fast_pow(a, i, p);
       int k = hash.find(j) == hash.end() ? -1 : hash[j];
       if(k >= 0 && (i * t - k) >= 0) return i * t - k;
    }
    return -1;
}

矩阵乘法

·定义
·矩阵乘法加速递推
·矩阵乘法转移状态

高斯消元法

具体不赘述，流程：构建增广矩阵->第i个方程第i项系数化一->下面的方程第i项系数化0->回代

//洛谷P3389 【模板】高斯消元法
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#define ll long long
using namespace std;
inline ll read(){
    ll s = 0, w = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')w = -1;ch = getchar();}
    while(ch >= '0' && ch <= '9') s = s * 10 + ch - '0',ch = getchar();
    return s * w;
}
const int MAXN = 110;
int n;
double M[MAXN][MAXN], ans[MAXN];
int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i)
       for(int j = 1; j <= n + 1; ++j)
          scanf("%lf", &M[i][j]);
    for(int i = 1; i <= n; ++i){
       int r = i;
       for(int j = 1; j <= n; ++j) if(fabs(M[j][i]) > 1e-8) r = j; //找到第一个第i项系数不为0的 
       if(r != i) for(int j = 1; j <= n + 1; ++j) swap(M[i][j], M[r][j]);   //和第i行交换 
       if(fabs(M[r][i]) < 1e-8){ printf("No Solution
"); return 0; }    //如果不存在（第i项系数都为0），则无解 
       double tmp = M[i][i];
       for(int j = 1; j <= n + 1; ++j)
          M[i][j] /= tmp;             //第i项系数化1 
       for(int j = i + 1; j <= n + 1; ++j){  //把其它方程第i项的系数去掉 
          tmp = M[j][i] / M[i][i];
          for(int k = 1; k <= n + 1; ++k)
             M[j][k] -= tmp * M[i][k];
       }
    }
    ans[n] = M[n][n + 1];
    for(int i = n - 1; i; --i){      //回代 
       ans[i] = M[i][n + 1];
       for(int j = i + 1; j <= n; ++j)
          ans[i] -= M[i][j] * ans[j];
    }
    for(int i = 1; i <= n; ++i) printf("%.2lf
", ans[i]);
    return 0;
}

组合计数

·排列：(A_n^m=frac{n!}{(n-m)!})
·组合：(C_n^m=frac{n!}{m!(n-m)!})
·杨辉三角：(C[n][m]=C[n-1][m-1]+C[n-1][m]) 边界(C[i][0]=1(0<=i<=n))
·二项式定理：((a+b)^n=sumlimits_{k=0}^{n}C_n^ka^kb^{n-k})
·(Catalan)数：(Cat_n=frac{C_{2n}^n}{n+1})
·(Lucas)定理：(C_n^m=C_{nmod p}^{mmod p} imes C_{n/p}^{m/p})
·容斥原理：奇加偶减

概率与数学期望

0/1分数规划

博弈论

·(NIM)游戏：获胜条件：(A_1 oplus A_2 oplus ... oplus A_n eq 0)
·(SG)函数：该点能到达的所有点的(SG)函数的集合的(mex)函数

感觉还是有点懵。。