数学

目录

• 中国剩余定理
• 扩展中国剩余定理 可以到这里（链接）这里学习，但是代码还是看我的吧
• 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
",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)<<"
"; 
	}
	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
");
			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
",(t%c+c)%c);
				p=true;
				break;
			}
		}
		if (!p)
			printf("no solution
");
	}
	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
");
		return 0;
	}
	if(p==32150321751LL){
		printf("No
");
		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
");
	else printf("No
");
	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
",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("
");
    }
    return 0;
}