最近在二中苦逼地上课，天天听数论（当然听不懂）
但是，简单的还是懂一点的
1.欧几里得算法
说得这么高级干什么，gcd入门一个月的人都会吧，还需要BB？
证明可参照其他博客（不会），主要就是gcd(a,b)=gcd(b,a%b);
特殊的，gcd(a,0)=gcd(0,a)=a;
然后一行
int gcd(int m,int n) { return n?gcd(n,m%n):m; }
2.扩展欧几里得
在班里天天看紫书，终于会打(背）了。
专门对于形如 ax+by=d(a,b,d为常数，d=gcd(a,b)) 的不定方程求整数解
证明可参照其他博客（不会），主要也是gcd(a,b)=gcd(b,a%b)（真有道理）
void exgcd(int a,int b,int &x,int &y)
{
if (!b) { x=; y=; return; }
int r=a%b,m=a/b;
exgcd(b,r,y,x);
y-=x*m;
}
然后这组解满足|x|+|y|最小
其实记代码也是可以的啦。
3.快速幂
快速幂，一个入门一个月的人都会的算法，主流有二分和快速幂两个版本。
原理不多说，一个是把a^n拆成两个相同的部分再递归求之。一个是不停增大初始部分然后得解。
只不过一个是二分，一个是倍增了啦。
<1>二分
int quick_pow(int a,int n,int p) //a^n % p
{
if (!n) return ;
int res=quick_pow(a,n/,p);
res=(long long) (res*res)%p;
if (a%) res=(long long) (res*a)%p;
return res;
}
<2>位运算
int Quick_pow(int a,int n,int p) //同上
{
int res=;
while (n)
{
if (n&) res=(long long) (res*a)%p;
a=(long long) (a*a)%p;
n=n>>;
}
return res;
}
篇幅还算挺大，代码都是刚刚重打的，导致我看到的一道BZOJ的巨水题没时间打了。
至于逆元，欧拉函数什么的。。。
一脸蒙逼。