math数学部分

gcd最大公約数(ユークリッドアルゴリズム,反復形式)

int gcd(int a,int b)//    
{
	int m,n,r;
	m=a>=b?a:b;//m>=n
	n=a<b?a:b;
	r=m%n;
	while(r!=0)
	{
		m=n;
		n=r;
		r=m%n;
	}
	return n;
}

lcm最小公倍数

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

gcdの最適化、Steinアルゴリズム+ビット演算、大きい整数を計算することができます

int gcdcore(int a,int b)
{
  if (a==0) return b;
  if (b==0) return a;
  while ((a & 0x1)==0)
  {
    a=a>>1;
  }
  if (a<b)
  {
    b=(b-a)>>1;
    return gcdcore(b,a);
  }
  else
  {
    a=(a-b)>>1;
    return gcdcore(a,b);
  }
}
int gcd_fast(int a,int b)//stein  +     
{
  int c=0;
  while (((a & 0x1)==0)&&(( b & 0x1 )==0))
  {
    a=a>>1;
    b=b>>1;
    c++;
  }
  if ((a & 0x1) == 0)
  {
    a=a>>1;
    return gcdcore(a,b)<<c;
  }
  else
    return gcdcore(b,a)<<c;

}

拡張ユークリッドアルゴリズム

int ex_gcd(int a,int b,int &x,int &y)
{
  int tmp,ans;
  if(b==0)
  {
    x=1;
    y=0;
    return a;
  }
  ans=ex_gcd(b,a%b,x,y);
  tmp=x;
  x=y;
  y=tmp-(a/b)*y;
  return ans;
}

拡張ユークリッドアルゴリズム(反復形式)

int exgcd(int m,int n,int &x,int &y)//    
{
  int x1,y1,x0,y0;
  x0=1; y0=0;
  x1=0; y1=1;
  x=0; y=1;
  int r=m%n;
  int q=(m-r)/n;
  while(r)
  {
    x=x0-q*x1; y=y0-q*y1;
    x0=x1; y0=y1;
    x1=x; y1=y;
    m=n; n=r; r=m%n;
    q=(m-r)/n;
  }
  return n;
}

拡張ユークリッド乗算逆元

int cal(int a,int m)//    
{
  int x,y;
  int gcd=ex_gcd(a,m,x,y);
  if(1%gcd!=0)
    return -1;
  x*=1/gcd;
  m=abs(m);
  int ans=x%m;
  if(ans<=0)
    ans+=m;
  return ans;
}