数学

快速幂

　　计算a^b O(logb)

　　先求x=a^(b/2) ,再求a^b=x*x;

　　luoguP1226快速幂+取余

long long qpow(long long a,long long b,long long p)
{
    long long s=1;
    while(b>0)
    {
        if(b%2) s=s*a%p;
        a=a*a%p;
        b/=2;
    }
    return s;
}

逆元

　　3/7=3*1/7 所以1/7就是7的乘法逆元

　　mod意义下不能做除法，所以用乘法来代替，

　　3/7(mod 11)=3*8(mod 11)

　　1/7*7=1,7*8mod11=1;

　　P3811 乘法逆元，线性递推

费马小求逆元

　　（给定p）若p为质，且p不是a的约数，

　　根据费马小：a^(p-1)=1(mod p),所以a的逆元x=a^(p-2)

欧拉定理求逆元

　　若a，p互质，根据欧拉：a^Φ(p)=1(mod p),所以a的逆元是a^Φ(p)-1

　　Φ(p)是?: 对于整数p，Φ(p)表示小于等于p的与p互质的数的个数

GCD

　　更相减损术：gcd(a,b)=gcd(a-b,b);

　　辗转相除法，相当于优化过的更相减损术；

辗转相除

　　gcd(x,y)=gcd(x%y,y), O(log),why?:x%y<=x/2;

　　当y<=x/2时，x%y<y<=x/2;

　　当x/2<y<x时，x%y=x-y<x-x/2=x/2;

最小公倍数

　　lcm(a,b)=a*b/gcd(a,b);

扩展GCD

　　利用gcd思想可以求一组不定方程的解，给定a，b，求ax+by=gcd(a,b)的解；

　　其中符号a/b为下取整；

　　通过上面的方法只能求出无数个解其中的一个，

　　通解为：

无解的情况？？？

　　ax+by=c，这个方程什么时候时无解？

　　c不是gcd(a,b)的倍数时；

推广到一般

　　以上知道如何求ax+by=gcd(a,b)后，那么如何求ax+by=c（保证有解）呢？

　　我们令k=c/gcd,那就相当于求k(ax+by)=gcd(a,b)*k,

　　那么就求出ax+by=gcd(a,b)的解，再将解*k即可；

同余

　　什么是同余？a≡b(mod m) → a mod m=b mod m???

　　不对，上面的式子没有考虑负数的情况；

　　正确的解释为：a≡b(mod m) → (a-b) mod m=0;

EG:

　　求关于x的同余方程ax≡1(mod b)的最小正整数解，2<=a,b<=2*10^9;

　　将原式转化为exgcd形式，相当于求ax-by=1;

　　若a,b不互质肯定无解，用exgcd求出一组解，再求最小正整数解，

　　只是某一组解就能求最小？　　

　　根据x加上b/gcd(a,b)，同时y减去a/gcd(a,b)后，仍满足ax+by=c

　　我们就可以求出最小的整数解；

　　P1082同余方程

/*
ax≡1( mod b)等价于ax+by=1。
那么题目就转化成求这个表达式x的最小值。
可以把1看成gcd(a,b),于是就变成求解exgcd了。
*/
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

int a,b,x,y;

int exgcd(int a,int &x,int b,int &y)
{
	if(b==0)
	{
		x=1;
		y=0;
		return a;
	}
	int s=exgcd(b,x,a%b,y);
	int k=x;
	x=y;
	y=k-a/b*y;
	return s;
}

int main()
{
	scanf("%d%d",&a,&b);
	exgcd(a,x,b,y);
	printf("%d",(x+b)%b);
	return 0;
}

同余方程组

　　%……￥&*……&……%，参见课件；

离散对数

　　%……￥&*……&……%，参见课件；

线性筛法求质数※

　　求[1,n]中所有的质数，n<=10^5? n<=10^7?

　　P3383线性求质数模板※　

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<cstring>
using namespace std;

int n,m,num,x;
int pri[10000002];
bool b[10000002];

bool judge(int n)
{
	for(int i=2;i<=n;++i)
	{
		if(!b[i]) pri[++num]=i;
		for(int j=1;j<=num;++j)
		{
			if(i*pri[j]>n) break;
			b[i*pri[j]]=1;
			if(i%pri[j]==0) break;
                //这句话保证了每个数只会被筛O(1)次，只会被自己最小的质因子筛掉
		}
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	b[1]=1;
	judge(n);
	while(m--)
	{
		scanf("%d",&x);
		if(b[x]) printf("No
");
		else printf("Yes
");
	}
	return 0;
}

　　这个题，这份代码一定要注意的是bool b数组0和1对应的到底是还是不是质数！

欧拉函数

　　公式？

线性筛法求欧拉函数

for(int i=2;i<=n;++i)
{
	if(!b[i]) 
	{
		pri[++num]=i;
		olar[i]=i-1;
	}
	for(int j=1;j<=num;++j)
	{
		if(i*pri[j]>n) break;
		b[i*pri[j]]=1;
		if(i*pri[j]!=0)
			olar[i*pri[j]]=olar[i]*(pri[j]-1);
		if(i%pri[j]==0)
		{
			olar[i*pri[j]]=olar[i]*pri[j];
			break;
		} 
	}
}
//相当于线性筛素数的时候顺道求出欧拉函数

　　非常有必要解释一下pri和olar这两个数组的意义，：

　　pri记录1~n中所有的素数，也就是说，pri[i]表示的是第i个质数是多少，；

　　olar当然就是欧拉函数了，olar[i]表示的是1~i中质数的个数，；

EG：

　　给出一个数n，求比n小且与n互质的数的和，n<=10^7;

　　答案就是n*olar[n]/2,互质的数是一对的，

　　gcd(a,n)=gcd(n-a,n)=1;

组合数

　　有序：n=3有6（n！）种排列，

　　无序：n！种算作一种，那么就有（n！-1）种都是重复的；

　　※放挡板问题；（不能解决0）

　　※0的话就先都+1，最后再-1；

　　先要知道杨辉三角：　　

　　1
　　1 1
　　1 2 1
　　1 3 3 1
　　1 4 6 4 1
　　1 5 10 10 5 1

　　杨辉三角的性质:

　　第n行的元素个数有n个;
　　第n行的所有元素之和为2*(n-1)?;
　　第n行第m个数的值为C(n-1, m-1),其中C为组合数;
　　(a+b)n展开后的各项系数等于第n+1行的值;
　　第n行第m个数的奇偶判断,及C(n-1,m-1)的奇偶判断:
　　(m-1)&(n-1)==(m-1)? 奇:偶;
　　(证明见http://www.cnblogs.com/Muia/p/5746491.html)

　　杨辉三角的应用:

　　最好的应用之一就是减少求组合数的复杂度:
　　将杨辉三角的值打印出来后,只需要查表即可得到正确结果,
　　这个对于求排列组合数非常有用;

另外一种Lucas定理

　　#%……￥%……&￥#@￥%

　　（常与数位DP结合，）

求组合数的另一种方法

　　给定o<=n<=m<=10^5,1<p<10^9;

　　q组数据，计算C(m,n)mod p;

　　※预处理出阶乘，和阶乘的逆元，直接计算???；O(m+n+q);

一些组合数有用的公式

　　要特别知道的是5和4；

容斥原理

　　eg：一道小学奥数，

　　答案为：4+17+18+15-6-6-5+2=39

　　容斥原理图：

斐波那契数列　　

　　f(0)=1,f(1)=1；
　　f(n)=f(n-1)+f(n-2),n>=2

卡特兰数　　

　　C(1)=1；
　　C(n+1)=C(1)C(n)+C(2)C(n-1)+...+C(n)C(1)

Eg：

　　n个数要进栈然后出栈，问出栈顺序有多少种？　

　　设f(n)为n个数的答案，枚举最后一个出栈的为k，那么

　　P1044 卡特兰数，栈（两种操作）

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
int main()
{
    int n;
    long long int f[100000];
    cin>>n;
    f[0]=f[1]=1;
    for(int i=2;i<=n;i++)
        f[i]=f[i-1]*(4*i-2)/(i+1);
    cout<<f[n];
}

Eg：

　　给定n个节点，求能生成多少个不同形状的二叉树?

　　设f(n)为n个数的答案,枚举左子树大小为k