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