数论

我是菜鸡
我是一个能把map用RE的菜鸡
模拟只会猜题意贪心刚好过样例
搜索不行剪枝难递归时常爆个栈
数学不好先打表 string只能KMP
DP只会套模板组合数学看运气
图论上来死八法计算几何瞎暴力
博弈打成DFS 数论只会GCD

只会gcd怎么行
天天被那些数论大火题爆踩Orz
菜鸡要崛起

GCD

额我们还是从简单的开始

gcd，最大公因数，
指两个或多个整数共有约数中最大的一个。

求它的方法有很多。

暴力

O(n)枚举即可

因数分解

把这些数分别分解质因数，然后在各个共有的素因数里，取出指数最小的乘方相乘即得最大公因数,O(???)

以上是2种naïve的求法。

学了数论，可以知道曾经有位大牛欧几里德给我们研究出了一种很cool的算法：

辗转相除法

(=欧几里德算法)

用较小数除较大数，再用出现的余数（第一余数）去除除数，再用出现的余数（第二余数）去除第一余数，如此反复，直到最后余数是0为止。O(log n)

伪代码如下

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

但好像递归的常数很大来着
我们还可以把它再优化一下
让它20% cooler
具体来说就是应用xor的特性
可以把它mo改成这个形式

int gcd(int a,int b)
{
    while(b)b^=a^=b^=a%=b;
    return a;
}

就是酱紫

欧拉函数

一般叫做 ~~fai~~ phi。
这么写

φ

欧拉函数是小于n的正整数中与n互质的数的数目。(但是φ(1)=1)

欧拉函数的公式是

[varphi (x) = x imes prod^n_{i=1} (frac{p_i -1}{p_i}) ]

其中(p1,p2,... ,pn)为(x)的所有质因数。* 每一个质因数只能算一次！

代码可以写成这个样子

int fai(int x)
{
    int tmp=x;register int i;
    for(i=2;i*i<=x;i++)if(x%i==0){tmp=tmp*(i-1)/i;while(x%i==0)x/=i;}
	if(x>1)tmp=tmp*(x-1)/x;return tmp;
}

扩展欧几里德算法

还记得之前那个欧几里德算法么
可以用来算gcd
现在把它拓展一下
就可以求解像这样的方程式

[ax + by = gcd(a,b) ]

中的(x)和(y).

问题来了
怎么球

欧几里德算法停止的状态是:a= gcd,b = 0,
这时候只要 a = gcd 的系数是 1 ，
就可以得到 (a*1 + b*0 = gcd)

当然这是最终状态，但是我们是否可以从最终状态反推到最初的状态呢？

假设当前我们要处理的是求出 a 和 b的最大公约数，
并求出x和y使得(a*x + b*y= gcd)，
而我们已经求出了下一个状态：b 和 a%b 的最大公约数，
并且求出了一组x1 和y1 使得：((amod b)*y1+b*x1= gcd)，
那我们怎么找出它们的关系呢?

我们知道： $ a mod b=a-(int)(a/b)b ( 那么，我们可以进一步得到： )gcd = bx1 + (a-(a/b)b)y1( )gcd = bx1 + ay1 – (a/b)by1( )gcd = ay1 + b(x1 – a/b*y1)$

我们求出来了x和y使得(a*x + b*y= gcd)，
然后......
$ x leftarrow y1( ) y leftarrow x1 – a/b*y1$

可以这么写

void gcdex(int a,int b,int &d,int &x,int &y)
{
	if(!b)d=a,x=1,y=0;
	else gcdex(b,a%b,d,y,x),y-=x*(a/b);
}

(d就是gcd(a,b))

乘法逆元

https://www.luogu.org/problem/show?pid=1082 .

求关于 x 的同余方程(ax ≡ 1 (mod b))的最小正整数解。

这不就是一道裸的求逆元题么
等会儿,逆元是什么?

对于正整数a和b，如果有(ax ≡ 1 (mod b))，
那么把这个同余方程中的x最小正整数解叫做a mo b的逆元.

逆元可以用上面的那个扩展欧几里德算法得出.

void gcdex(int a,int b,int &d,int &x,int &y)
{
	if(!b)d=a,x=1,y=0;
	else gcdex(b,a%b,d,y,x),y-=x*(a/b);
}

这是刚才那段代码.

你问我逆元有什么用?
做题时如果结果过大一般都会让你mo一个数，而这个数一般是个非常巨大的质数，加减乘与mo运算的顺序交换不会影响结果，但是除法不行.
而有些丧心病狂的题目就是要mo一个巨大的质数，如果原本的结果中有除法，比如除以一个数n,直接可以让它精度原地起爆.
为了~~维护世界的和平~~防止意外出现,我们就可以把它换成乘n的逆元(倒数),效果都一样,只是更安全.

不过用扩欧求逆元有个条件
就是

[gcd(a,b)mod b=1 ]

...

球逆元的话可以在上面那基础上再加一些代码

int inv(int a,int p)
{
    int d,x,y;
    gcdex(a,p,d,x,y);
    return d==1?(x+p)%p:-1;//gcdex有时候会出负数,所以要加一下再mo
    //还有,d是gcd(a,b)
}

顺便贴个模板题Luogu 1082的题解

#include<iostream>
#include<iomanip>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
inline int gotcha()
{
    register int _a=0;bool _b=1;register char _c=getchar();
    while(_c<'0' || _c>'9'){if(_c=='-')_b=0;_c=getchar();}
    while(_c>='0' && _c<='9')_a=_a*10+_c-48,_c=getchar();
    return _b?_a:-_a;
}
void gcdex(int a,int b,int &d,int &x,int &y)
{
    if(!b)d=a,x=1,y=0;
    else gcdex(b,a%b,d,y,x),y-=x*(a/b);
}
int inv(int a,int p){int d,x,y;gcdex(a,p,d,x,y);return d==1?(x+p)%p:-1;}
int main()
{
    register int a=gotcha(),p=gotcha(),ans=inv(a,p);
    if(ans>=0)printf("%d",ans);//else puts("Fuck you");
    return 0;
}

施工中
但最近不想写(2)了