数论模板合集(更新中)

注:部分为未开(long long)且未取模

#include<cstdio>
#include<algorithm>
#include<ctype.h> 
#include<vector>
#include<queue>
#include<cstring>
#define lowbit(x) (x&-x)
#define ll long long
#define ld double
#define reint register int
#include<map>
#include<stdlib.h>
#include<ctime>
#define mod 19260817
using namespace std;

const int maxn=(1e7*2)+2;
ll n,p,inv[maxn];
inline ll add(ll a,ll b,ll p){return a+b<p?a+b:a+b-p;}
inline ll mul(ll a,ll b,ll p){return a*b<p?a*b:a*b%p;}
inline ll add(ll a,ll b){return a+b<mod?a+b:a+b-mod;}
inline ll mul(ll a,ll b){return a*b<mod?a*b:a*b%mod;}

struct arr{
    ll n,m;
    ll a[21][21];
    ll *operator[](int b){return a[b];}
    inline arr(ll c=0,ll d=0)
    {
        memset(a,0,sizeof(a));
        n=c,m=d;
    }
    arr operator*(arr b) const
    {
        arr c;
        c.n=n;c.m=b.m;
        for(reint i=0;i<n;i++)
        for(reint j=0;j<c.m;j++)
        for(reint k=0;k<m;k++)
        c[i][j]=add(c[i][j],mul(a[i][k],b[k][j]));
        return c;
    }
    arr operator*=(arr a){
        *this=*this*a;
        return *this;
    }
    arr operator^(ll b)
    {
    	arr ans;
    	ans=arr(n,m);
    	for(reint i=0;i<n;i++)
    	ans[i][i]=1;
    	while(b)
    	{
      		if(b&1ul) ans*=*this;
      	  	*this*=*this;
       	 	b>>=1ul; 
    	}
    	return ans;
    }
};

void getni(ll p)
{
	inv[1]=1;
    for(int i=2;i<=n;i++) inv[i]=mul(add(-p/i,p,p),inv[p%i],p);
}

int mg(int a,int b,int c)
{
    int ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%c;
        b>>=1;
        a=a*a%c;
    }
    return ans;
} 

int exgcd(int a,int b,int &x1,int &y1)
{
    if(!b)
    {
        x1=1,y1=0;
        return a;
    }
    int x2,y2;
    int d=exgcd(b,a%b,x2,y2);
    x1=y2,y1=x2-(a/b)*y2;
    return d;
}

int crt(int a[],int m[],int n)
{
    int M=1,ans=0;
    for(int i=1;i<=n;i++) M*=m[i];
    for(int i=1;i<=n;i++)
    {
        int ni,tmp;int mi=M/m[i];
        exgcd(mi,m[i],ni,tmp);
        if(!ni) ni=M;
        ans=(ans+M*ni*a[i])%M;
    }
    return ans<0?ans+M:ans;
} 

int excrt(int a[],int m[],int n)
{
    int M=m[1],t,ni,tmp,d,ans=a[1];
    for(int i=2;i<=n;i++)
    {
        d=exgcd(M,m[i],ni,tmp);
        if((a[i]-ans)%d) return -1;
        t=m[i]/d,ni*=(a[i]-ans)/d,ni=(ni%t+t)%t;
        ans+=M*ni,M=M/d*m[i],ans%=M;
    }
    return ans<0?ans+M:ans;
}

int main(){}