一 .数学基础
1.模运算的基本法则与相关定理
1)(a+b)%p=((a%p)+(b%p))%p
(a-b)%p=((a%p)-(b%p)+p)%p
a*b%p=((a%p)*(b%p))%p
(a^b)%p=((a%p)^b)%p (本质就是乘法)
2)费马小定理，欧拉定理，扩展欧拉定理
费马小定理：p为素数，a,p互质，a^(p-1)%p=1
欧拉定理：a,p互质a^(phi(p))%p=1 (其实是费马小定理的一般情况，phi(n)表示1~n中和n互质的数的个数)
扩展欧拉定理：①a,p互质，有a^b%p=a^(b%phi(p))%p ②a,p不互质，b<phi(p)，有a^b%p=a^b%p ③a,p不互质，且b>=phi(p),有a^b%p=a^(b%phi(p)+phi(p))%p
3)逆元的求法
①exgcd ②费马小定理/欧拉定理 ③O(n)求逆元 ④n!的逆元可以计算出最后一个然后往前倒推
ps:
1 void exgcd(int a,int b,int &x,int &y){ 2 if(!b)x=1,y=0; 3 else { 4 exgcd(b,a%b,x,y); 5 int tmp=y;y=x-a/b*y;x=tmp; 6 } 7 }
phi函数求法将会在后面介绍。
2.部分数学函数
1)三角函数与反三角函数
sin(x) cos(x) tan(x) acos(x) asin(x) atan(x) 另有atan2(x,y) 暂时没看出来意义何在
可以利用asin(1)来得到Π/2的值
2)指数与对数函数
exp(x)表示e^x pow(x,y)表示x^y sqrt(x) log(x)以e为底的对数 log10(x)和log2(x)同理
3)随机数函数
rand()随机生成一个short型的数字 需要srand(x)写在最开始来选取第x张随机数表，否则默认第一张，为了方便我们通常写srand(time(NULL))来使得每次都用的不同的随机数表
4)其他
ceil(x)上取整 floor(x)下取整 fabs(x)/abs(x)取绝对值(未发现区别) modf(x,&y)返回x的小数部分，将其整数部分赋值到y上 fmod(x,y)表示x%y(dl型)