数学

中国剩余定理
扩展中国剩余定理可以到这里（链接）这里学习，但是代码还是看我的吧
Lucas卢卡斯定理
bsgs(北上广深，拔山盖世)
Miller-Rabin素数测试
高斯消元
矩阵快速幂

中国剩余定理

#include<iostream>
#include<cstdio>
#define int long long 
using namespace std;
long long n,x,y,M;
int a[100],mod[100];
void exgcd(int a,int b,int &x,int &y) {
    if(b==0) {
        x=1;y=0;
        return;
    }
    exgcd(b,a%b,x,y);
    int tmp=x;
    x=y;
    y=tmp-a/b*y;
}

int inv(int a,int b) {
    exgcd(a,b,x,y);
    while(x<0)x+=b;
    return x;
}

int CRT()
{
    int ans=0;
    for(int i=1;i<=n;++i)
    {
        int m=M/mod[i];
        int Inveres=inv(m,mod[i]);
        int w=((Inveres*m*a[i])%M+M)%M;
        ans+=w;
        ans%=M;
    }
    return ans;
}
main()
{
    scanf("%lld",&n);M=1;
    for(int i=1;i<=n;++i) {
        scanf("%lld%lld",mod+i,a+i); 
        M*=mod[i];
    }
    int ans=CRT();
    printf("%lld",ans); 
    return 0;
}

扩展中国剩余定理可以到这里（链接）这里学习，但是代码还是看我的吧

2018.8.3更新解释炒鸡详细，

#include <iostream>
#include <cstdio>
#define ll long long
#define maxn 100100
using namespace std;
ll n;
ll z[maxn],mod[maxn];
ll mul(ll a,ll b,ll mod)
{
    ll ans=0;
    while(b)
    {
        if(b&1) ans=(ans+a)%mod;
        a=(a+a)%mod;
        b>>=1;
    }
    return ans;
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{
    if(!b) {
        x=1;y=0;
        return a;
    }
    ll zz=exgcd(b,a%b,x,y);
    ll tmp=x;
    x=y;
    y=tmp-a/b*y;
    return zz;
}
ll EXCRT()
{
    ll x,y,k;
    ll M=mod[1],ans=z[1];
    for(ll i=2;i<=n;++i)
    {
        ll a=M,b=mod[i],c=(z[i]-ans%b+b)%b;
        ll gcd=exgcd(a,b,x,y),bg=b/gcd;
        if(c%gcd) return -1;
        x=mul(x,c/gcd,bg);
        ans+=x*M;
        M*=bg;
        ans=(ans%M+M)%M;
    }
    return ans; 
} 
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;++i)
        scanf("%lld%lld",&mod[i],&z[i]);
    printf("%lld\n",EXCRT());
    return 0;
}

Lucas卢卡斯定理

p不大的时候也可以用线性求逆元详见博客

#include <iostream>
#define int long long
#define maxn 100007
using namespace std;
int n,m,p;
int fac[maxn];
int fast_pow(int a,int b,int mod)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
        b>>=1;
    }
    return ans;
}
int C(int a,int b,int p)
{
    if(b>a) return 0;
    return (fac[a]*fast_pow(fac[b],p-2,p)%p*fast_pow(fac[a-b],p-2,p)%p)%p;
}
int lucas(int a,int b,int p)
{
    if(!b) return 1;
    return C(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
} 
main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n>>m>>p;
        fac[0]=1;
        for(int i=1;i<=p;++i)
            fac[i]=(fac[i-1]*i)%p;
        cout<<lucas(n+m,n,p)<<"\n"; 
    }
    return 0;
}

bsgs(北上广深，拔山盖世)

Baby-Step-Giant-Step算法

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
#include<cmath>
#define ll long long
using namespace std;
ll a,b,c,m,f[10000000];
map<long long,int> mp;
ll  fast_pow(ll x) { 
    ll sum=1;
    ll aa=a;
    while (x>0) {
        if (x&1)
            sum=(sum*aa)%c;
        x=x>>1;
        aa=(aa*aa)%c;
    }
    return sum;
}
int main() {
    mp.clear();
    while (scanf("%lld%lld%lld",&c,&a,&b)!=EOF) {
        mp.clear();
        if (a%c==0) {
            printf("no solution\n");
            continue;
        }
        int p=false;
        m=ceil(sqrt(c));
        ll ans;
        for (int i=0; i<=m; i++) {
            if (i==0) {
                ans=b%c;
                mp[ans]=i;
                continue;
            }
            ans=(ans*a)%c;
            mp[ans]=i;
        }
        ll t=fast_pow(m);
        ans=1;
        for (int i=1; i<=m; i++) {
            ans=(ans*t)%c;
            if (mp[ans]) {
                int t=i*m-mp[ans];
                printf("%d\n",(t%c+c)%c);
                p=true;
                break;
            }
        }
        if (!p)
            printf("no solution\n");
    }
    return 0;
}

Miller-Rabin素数测试

#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline ll mul(ll a,ll b,ll mod) {
    a%=mod;
    b%=mod;
    ll ans=0;
    for(; b; a+=a,b>>=1) {
        if(b&1) ans+=a;
        ans%=mod;
        a%=mod;
    }
    return ans;
}

inline ll qpow(ll a,ll b,ll mod) {
    a%=mod;
    ll ans=1;
    for(; b; a=mul(a,a,mod),b>>=1) {
        if(b&1) ans=mul(ans,a,mod);
        a%=mod;
        ans%=mod;
    }
    return ans;
}

int main() {
    srand(time(0));
    ll p;
    cin>>p;
    int js=0;
    if(p==2LL) {
        printf("Yes\n");
        return 0;
    }
    if(p==32150321751LL){
        printf("No\n");
        return 0;
    }
    for(int i=1; i<=20; ++i) {
        ll x=rand()%(p-2)+2;
        ll tmp=qpow(x,p-1,p);
        if(tmp==1LL) js++;
    }
    if(js==20) printf("Yes\n");
    else printf("No\n");
    return 0;
}

高斯消元

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

const double eps=1e-6;
int n;
double a[110][110];
double ans[110];

int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
          for(int j=1; j<=n+1; ++j)
            scanf("%lf", &a[i][j]);
            
    for(int i=1; i<=n; ++i) {
        int pivot=i;
        for(int j=i+1; j<=n; ++j)
            if(fabs(a[j][i]) > fabs(a[pivot][i])) pivot=j;
        if(abs(a[pivot][i]) < eps) {//精度丢失 
            printf("No Solution");
            return 0;
        }
        if(pivot!=i) swap(a[i],a[pivot]);
        double tmp=a[i][i];
        for(int j=i; j<=n+1; ++j) {
            a[i][j]/=tmp;
        }
        for(int j=i+1;j<=n;j++) {
            tmp=a[j][i];//倍数关系 a[i][i]=1 
            for(int k=i;k<=n+1;k++) {
                a[j][k]-=a[i][k]*tmp;
            }
        }
    }
    
    ans[n]=a[n][n+1];
    for(int i=n-1; i>=1; i--) {
        ans[i]=a[i][n+1];
        for(int j=i+1; j<=n; ++j)
           ans[i]-=a[i][j]*ans[j];
    }//回带 
    for(int i=1;i<=n;++i)
        printf("%.2lf\n",ans[i]);
}

矩阵快速幂

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring> 
#define ll long long
using namespace std;
const int X = 100+10;
const int mod = 1e9+7;
ll m,n;
struct edge
{
    ll m[X][X];
}ans,res;
inline edge mul(edge a,edge b)
{
    edge tmp;
    for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
        tmp.m[i][j]=0;
    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){ 
            for(int k=1;k<=n;++k){
                tmp.m[i][j]=(tmp.m[i][j]+(a.m[i][k]*b.m[k][j])%mod)%mod;
            }
        }
    }
    return tmp; 
}
void fpow(ll a)
{ 
    for(int i=1;i<=n;++i)
        ans.m[i][i]=1;
    while(a)
    {
        if(a&1)
          ans=mul(ans,res);
        a>>=1;
        res=mul(res,res);
    }
}
int main()
{ 
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;++i)
    {
        for(ll j=1;j<=n;++j)
           scanf("%lld",&res.m[i][j]);
    }
    fpow(m);
    for(ll i=1;i<=n;++i)
    {
        for(ll j=1;j<=n;++j)
        printf("%lld ",ans.m[i][j]%mod);
        printf("\n");
    }
    return 0;
}