GCD + LCM + 素数打表 + 快速幂

几个常用的板子

1
gcd为两个数的最大公因数
gcd模板

int gcd (a , b ) {
return  !b?a:gcd(b,a%b) ;
}

2
lcm为两个数的最小公倍数

lcm(a,b)=(a*b)/gcd(a,b)

3
素数打表

//求0~100000以内的素数
  //（下标为0的是素数，下标不为0的为合数）
  bool str[100010];
  void prime()
  {
   str[1]=1;
   for(int i=2;i<100010;i++)
   if(!str[i])
   {
    //可以在这里加数组记录素数 
    for(int j=i*2;j<=100010;j=j+i)
    str[i]=1;
   }
  }

memset(vis,0,sizeof vis);
vis[1]=1;
for(int i=2;i<=n;i++)
{
	for(int j=i*2;j<=n;j=j+i)
	vis[j]=1;
}

欧拉筛，求每一个数的欧拉函数的值，结果保存在数组a中。

欧拉函数phi(n)是数论中非常重要的一个函数，其表示1到n-1之间，与n互质的数的个数。

memset(a,0,sizeof a);
a[1]=1;a[2]=0;
for(int i=2;i<=2000000;i++)
{
	if(!a[i])
	for(int j=i;j<=2000000;j+=i)
	{
		if(!a[j]) a[j]=j;
		a[j]=a[j]/i*(i-1);
	} 
}

4
快速幂
求 a^b%c

int ksm(int a,int b,int c)
{
 int ans=1;
 a=a%c;
 while(b>0) 
 {
  if(b%2==1)
  ans=ans*a%c;
  b=b/2;
  a=(a*a)%c;
 }
 return ans;
}

打赏