快要比赛了，要抓紧时间力！

1.拓展欧几里得exgcd

用于求ax+by=c的解，当c = k * gcd(a, b)时有解。

解集为\(x = x_0 + k * (b / d), y = y_0 - k * (a / d)\)，其中d为gcd(a, b)。

不难发现，x的最小正整数解一定是mod(b / d)意义下的，所以一般对方程的解法是先将x扩大c / d倍，再模上b / d即可。

模板题：P1008 - 同余问题 - ETOJ (eriktse.com)

代码模板：

int exgcd(int a,int b,int &x,int &y)
{
    if(!b)return x = 1, y = 0, a;
    int d = exgcd(b, a % b, y, x);
    y -= a / b * x;
    return d;
}
 
signed main()
{
    int A, B, P, X, Y;cin >> A >> B >> P >> X >> Y;
     
    int a = ((X - Y) % P + P) % P;
    int b = P, x, y, c = ((B - A) % P + P) % P;
     
    int d = exgcd(a, b, x, y);
    if(c % d)cout << "Impossible" << '\n';
    else
    {
        x = x * (c / d);
        int L = b / d;//X的模数(步长)
        cout << ((x % L) + L) % L << '\n';
    }
     
    return 0;
}

2.欧拉函数

欧拉函数phi(n)表示[1, n]中与n互质的数的个数。

单点求解复杂度O(sqrt(N))，遍历n的所有质因数p，然后乘上(p - 1) / p。

筛法类似于欧拉筛O(NlogN)，只需要在遇到质数p的时候给所有倍数乘上(p - 1) / p即可。

int phi[maxn];
void init_Euler(int n)
{
     for(int i = 1;i <= n; ++ i)phi[i] = i;
     for(int i = 2;i <= n; ++ i)
          if(phi[i] == i)for(int j = i;j <= n; j += i)phi[j] = phi[j] / i * (i - 1);
}

欧拉定理（条件是a、n互质）：

a^φ(n)≡1(mod n)

当要求a的多少次方等于1的时候，这个指数一定是phi(模数)的满足条件的因子。

同时欧拉函数还有一些特性：与n互质的数字一定成对出现，比如对于数字18，和它互质的数字有1, 5, 7, 11, 13, 17，不难发现其中(1, 17), (5, 13), (7, 11)分别成对出现且和为n。所以如果要计算[1, n]与n互质的所有的数之和，只需要用n乘上欧拉函数再除以二即可。

Expression:\(sum = \frac{n \times \phi(n)}{2}\)

3.费马小定理

这个用的太多了，如果p是一个质数且a, p互质，就有：

\(a^p = a(mod p)\)

这个可以用来求逆元，或者维护一些其他的东西。

4.Wilson定理

设p是一个素数，则有：

\((p - 1)! = -1 (mod p)\)

p - 1的阶乘在mod p意义下等于-1（也就是p - 1）。

5.常见的两种生成函数

第一种列表型多项式：

\(h = \sum_{i = 0}^{\inf} x^i = 1 + x + x^2 + ... = \frac{1}{1 - x}\)

一般用于处理组合类问题。

拓展：

第二种指数型多项式：

\(h = \sum_{i = 0}^{\inf} x^i/i! = x^0/0! + x/1! + x^2/2! + ... = e^x\)

一般用于处理排列类问题。

当x = kx时，只需代入即可，不难发现系数会变成k的i次方。

一些常见的多项式计算方法：

\((1 - x^k) = (1 - x) * (1 + x + x ^ 2 + .... + x ^{k-1})\)