【模板】数论算法

#include<bits/stdc++.h>
#define inf 2147483647
#define INF 9223372036854775807
using namespace std;
long long c[1010][1010];
int prime[1000010];
int is[1000010];
int res[1000010];
//组合数 
long long C(int n,int m,long long p)
{
    if(m>n)return 0;
    m=min(m,n-m);
	if(c[n][m])return c[n][m];
	if(m==0)return c[n][m]=1;
	if(m==1)return c[n][m]=n%p;
	c[n][m]=(C(n-1,m,p)+C(n-1,m-1,p))%p;
	return c[n][m];
} 
//log2
int log2(int x)
{
	double ans=log(x)/log(2);
	return (int)ans;
}
//快速幂
long long super_my(int a,int b,long long  p)
{
    if(b==0)return 1;
    if(b&1)return (a*super_my(a,b-1,p))%p;
    long long temp=super_my(a,b/2,p);
    return (temp*temp)%p;
}
//卢卡斯定理 
int Lukas(int n,int m,int p)
{
    if(m==0)return 1;
    
	return (C(n%p,m%p,p)*Lukas(n/p,m/p,p)%p)%p;
}
//欧几里得算法 
int gcd(int a,int b)
{
	return !b?a:gcd(b,a%b);
}
//拓展欧几里得算法 
int Exgcd(int a,int b,int &x,int &y)
{
	if(!b)
	{
		x=1;
		y=0;
		return a;
	}
	int r=Exgcd(b,a%b,x,y);
	int temp=y;
	y=x-a/b*y;
	x=temp;
	return r;
}
//解不定方程ax+by=c 
bool diophantine(int a,int b,int c,int &x,int &y)
{
	int gcd=Exgcd(a,b,x,y);
	if(c%gcd)return false;
	int k=c/gcd;
	x*=k;
	y*=k;
	return true;
}
/*!!!ps--------------------
	each_x=x+b/gcd*k;
	each_y=y-a/gcd*k;
*/
//卡特兰数 
long long Carter_LAN(int x)
{
	return C(x<<1,x,INF)/(x+1);
}
//欧拉筛法 
int sieve(int n)
{
	int cnt=0;
	memset(is,127,sizeof is);
	for(int i=2;i<=n;i++)
	{
		if(is[i])prime[++cnt]=i;
		for(int j=1;j<=cnt&&i*prime[j]<=n;j++)
		{
			is[i*prime[j]]=false;
			if(!(i%prime[j]))break;
		}
	}
	return cnt;
}
//素数判定 
bool is_prime(int x)
{
	for(int i=2;i<=sqrt(x);i++)
		if(!(x%i))return false;
	return true;
}
//质因数分解 
int divide(int x)
{
	int len=sieve(sqrt(x));
	for(int i=1;i<=len;i++)
	{
		while(!(x%prime[i]))x/=prime[i],res[i]++;
	}
	return x;
}
//除法取模(gcd(b,p)==1)
int mod(int a,int b,int p)//(a/b)%p
{
    if(gcd(b,p)!=1)return 0;
    if(!is_prime(p))return 0;
    return (a%p*(super_my(b,p-2,p)))%p;
}
int main()
{
	
	return 0;
}