快要比赛了，要抓紧时间力！
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})\)
文章评论