最大公约数–欧几里得算法 gcd(a,b)=gcd(b,a%b)

int gcd(int a,int b)
{
    
	if(b==0)
	{
    
		return a;
	}
	else
	{
    
		return gcd(b,a%b);
	}
} 

最小公倍数

int lcm(int a,int b)
{
    
	int d=gcd(a,b);
	return a/d*b;
}

分数的定义与化简

struct Fraction{
    
	int up,down;
}; 
//化简分数
Fraction reduction(Fraction result)
{
    
	if(result.down<0)
	{
    
		result.up=-result.up;
		result.down=-result.down;
	}
	if(result.up==0)
	{
    
		result.down=1;
	}
	else
	{
    
		int d=gcd(abs(result.up),abs(result.down));
		result.up/=d;
		result.down/=d;
	}
	return result;
} 

素数（也称质数）合数
素数的判断

bool isPrime(int n)
{
    
	if(n<=1)
	{
    
		return false;
	}
	int sqr=(int)sqrt(1.0*n);
	for(int i=2;i<=sqr;i++)
	{
    
		if(n%i==0)
		{
    
			return false;
		}
	} 
	return true;
} 

枚举素数的Eratosthenes筛法

int MAX=101;
int prime[101]={
    0};
int pnum=0;
bool isp[101]={
    false};
void findprime()
{
    
	for(int i=2;i<MAX;i++)
	{
    
		if(isp[i]==false)
		{
    
			prime[pnum++]=i;
			for(int j=i+i;j<MAX;j+=i)
			{
    
				isp[j]=true;
			}
		}
	}
}

质因子分解（在获得质数表的基础上解题）

struct factor{
    
	int x,cnt;
}fac[10];
int n=180;//需要被分解的数字
int num=0;
void fenjie(int n){
    
	int i=0;
	int m=n;
	while(prime[i]<=sqrt(m))
	{
    
		cout<<prime[i]<<endl;
		cout<<sqrt(m)<<endl;
		if(n%prime[i]==0)
		{
    
			fac[num].x=prime[i];
			fac[num].cnt=0;
			while(n%fac[num].x==0)
			{
    
				fac[num].cnt++;
				n=n/prime[i];
			}
			num++;
		}
		i++;
	}
	if(n!=1)
	{
    
		fac[num].x=n;
		fac[num++].cnt=1;
	}
}

额外基础知识：注意结构体使用 struct 或typedef strcut的不同情况，详见收藏夹
大整数运算
定义和读入

struct bign{
    
	int d[1000];
	int len;
	bign(){
    
		memset(d,0,sizeof(d));
		len=0;		
	}	
}; 

bign change(string str)//或是char str[] 
{
    
	bign a;
	a.len=str.length();
	for(int i=0;i<a.len;i++)
	{
    
		a.d[i]=str[str.length()-i-1]-'0';
	}
	return a;
}

大整数加法

bign add(bign a,bign b)
{
    
	bign c;
	int carry=0;
	for(int i=0;i<a.len||i<b.len;i++)
	{
    
		int temp=a.d[i]+b.d[i]+carry;
		c.d[c.len++]=temp%10;
		carry=temp/10;
	}
	if(carry!=0)
	{
    
		c.d[c.len++]=carry;
	}
	return c;
}

大整数减法

bign sub(bign a,bign b)
{
    
	bign c;
	for(int i=0;i<a.len||i<b.len;i++)
	{
    
		if(a.d[i]<b.d[i])
		{
    
			a.d[i+1]--;
			a.d[i]+=10;
		}
		c.d[c.len++]=a.d[i]-b.d[i];
	}
	while(c.len-1>=1&&c.d[c.len-1]==0)
	{
    
		c.len--;
	}
	return c;
} 

高精度*低精度

bign multi(bign a,int b)
{
    
	bign c;
	int carry=0;
	for(int i=0;i<a.len;i++)
	{
    
		int temp=a.d[i]*b+carry;
		c.d[c.len++]=temp%10;
		while(carry!=0)
		{
    
			c.d[c.len++]=carry%10;
			carry/=10;
		}
	}
	return c;
}

高精度÷低精度

bign divide(bign a,int b,int& r)
{
    
	bign c;
	c.len=a.len;
	for(int i=a.len-1;i>=0;i--)
	{
    
		r=r*10+a.d[i];
		if(r<b)
		{
    
			c.d[i]=0;
		}
		else
		{
    
			c.d[i]=r/b;
			r=r%b;
		}
	}
	while(c.len-1>=1&&c.d[c.len-1]==0)
	{
    
		c.len--;
	}
	return c;
}

扩展欧几里得算法 ax+by=gcd(a,b)此处为引用，因此在结束后传入的xy即为所求

int exgcd(int a,int b,int& x,int& y)
{
    
	if(b==0)
	{
    
		x=1;
		y=0;
		return a;
	}
	int g=exgcd(b,a%b,x,y);
	int temp=x;
	x=y;
	y=temp-a/b*y;
	return g;
}

扩展欧几里得方法主要运用于计算ax+by=c,用上述方法求解再乘c/gcd(a,b)即可，要求c%gcd(a,b)==0
同余数 逆元的求解
组合数
计算n！的末尾有多少个质因子p(可以用该算法算出n!末尾有几个零cal(n,5))

int cal(int n,int p)
{
    
	int ans=0;
	while(n)
	{
    
		ans+=n/p;
		n/=p;
	}
	return ans;
}

计算组合数Cnm(n在下m在上)

long long C(long long n,long long m)
{
    
	long long ans=1;
	for(long long i=1;i<=m;i++)
	{
    
		ans=ans*(n-m+i)/i;
	}
	return ans;
}

快速幂（计算的是a的n次方%m）

long long binaryPow(long long a,long long b,long long m) 
{
    
	if(b==0)
	{
    
		return 1; 
	}
	if(b%2==1)
	{
    
		return a*binaryPow(a,b-1,m)%m;
	}
	else
	{
    
		long long mul=binaryPow(a,b/2,m);
		return mul*mul%m;
	}
}

计算组合数Cnm(n在下m在上)%p

const int maxn=100000;
int prime[maxn] ;
int C(int n,int m,int p)
{
    
	int ans=1;
	for(int i=0;prime[i]<=n;i++)
	{
    
		int c=cal(n,prime[i])-cal(m,prime[i])-cal(n-m,prime[i]);
		ans=ans*binaryPow(prime[i],c,p)%p;
	}
	return ans;
}