アルゴリズム in C++

ysd@KLab > アルゴリズム

目的

忘れそうだけどよく使う(特にACMで)アルゴリズム。高速入力用。高速動作はあまりめざしてない。

ユークリッドの互除法

言わずもがな、a と b の最大公約数を返します。 
int gcd(int a, int b)
{
  if(b == 0) return a;
  else return gcd(b, a % b);
}

拡張版

ちょっと拡張。ax+by=gcd(a,b)を満たす x と y も返してくれます。 
int gcd2(int a, int b, int& x, int & y)
{
  int r1, r2, r3, x1, x2, x3, y1, y2, y3;
  r1 = a, x1 = 1, y1 = 0;
  r2 = b, x2 = 0, y2 = 0;
  while(r2 != 0) {
    int q = r1 / r2;
    r3 = r1 - q * r2; // r3 = r1 % r2;
    x3 = x1 - q * x2;
    y3 = y1 - q * y2;
    r1 = r2, r2 = r3;
    x1 = x2, x2 = x3;
    y1 = y2, y2 = y3;
  }
  x = x1, y = y1;
  return r1;
}

素因数分解

n の素因数を vector 型で返します。 
#include <vector>

vector<int>& fact(int n)
{
  vector<int> v;
  for( int i = 2 ; i * i <= n ; i++ ) {
    while( n % i == 0 ) {
      v.push_back( i );
      n /= i;
    } 
  }
  return v;
}