数系

double res;
int t = (int)res;  //切り下げ
int m = (int)(res+0.5); //四捨五入
int r;
if(res-t < 1e-9) r = t;
else r = t+1;   //切り上げ
//の　ceil関数を使う．
double ceil(double x)	n-1 < x <= n の整数

テスト用の最大値、最小値の算出

INF = 1 << 30;
EPS = 1e-9;

sqrt(A)をint型にしたいときの注意．
もしかすると、sqrt(64) = 8.0000001とか、sqrt(64) = 7.999999998とかになるかもしれない．
そのときに、( (int)sqrt(64) == 7)がtrueになることもなくはない．そこで安全を期すことにする．

Aが整数の二乗の数か判定とかしたいときは、(もちろん、Aは整数でなければならないので、必然的にint型 or  long型)

double tmp = sqrt(num - i*i) - (int)sqrt(num - i*i + 0.5);
  if(fabs(tmp) < eps) {
    ans.push_back( Dot(i, (int)sqrt(num-i*i)) );
  } 
}
とか、
(int)sqrt(A) + 0.5  とかした方が安心．
//とりあえず、本体に影響がないように0.5をかけることを頭の隅に入れておく．

n乗のときは全てほぼ同じ。
//超慎重に。ここまでやれば鬼に金棒。ちょっとやりすぎのような気がしないでもない。
int tmp = (int)cbrt(i+0.5);
if(fabs(cbrt(i) - tmp) < eps) {
  ..
}

負のときの余り

int main() {
  int i = -16;
  cout << i % 10 << endl;  //-6
}

平均を求めるとき、

int型, long long型なら、数が大きくなりすぎてオーバーフローをおこすかもしれない。
for(int i = 0; i < sz; i++) {
　　ave += money[i]; //ここで桁があぶれる。
}
ave = ave/sz;

なので、次の書き方が望ましい。
for(int i = 0; i < sz; i++) {
  ave += money[i]/sz; rem += money[i]%sz;
}
ave += rem/sz; //これで桁があぶれず、なおかつ小数点を切り捨てずにすむ。

2の累乗

//powを使いたいが、int型の引数をとらないので、不便．
int i = 1 << p;
//とするとすっきりする．

0に初期化

int arr[sz] = {0};
//memsetとか、fillとか、使わなくてよい．

最大公約数

int gcd(int a, int b) {
	//if(a < b) swap(a, b);  //a is always bigger than b
	if(a % b == 0) return b;
	return gcd(b, a % b);  //b > a % b
}

最大公倍数も一応。

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

場合の数（負の数と0は考慮していない．）
Permutation::nPr

long long permutation(int n, int r) {
  long long ans = 1;
  if(n < r) return 0;  //eg.)3P5 = 0
  for(int i = n; i > n-r; i--) {
    ans *= i;
  }
  return ans;
}
//function recursive is a bit slow so I used the control structure, that is 'for'.

数え上げ、重複要素の排除
配列(vector t;)が重複しているので、数を数える．

set s;
for(vector::iterator it = t.begin(); it != t.end(); it++) {
  s.insert(*it);
}
return s.size();
//または、
return set(s.begin(), s.end()).size();  //の1行ですっきりかける

桁の処理

int digitsum(int num) {
  int res = 0;
  while(num) {
    res += num % 10; num /= 10;
  }
  return res;
}

円周率とか、sin, cosとか、

#include 
//e  :: M_E
//π :: M_PI
//log :: 

平方根は#include sqrtでいいけど、
立方根は

double cbrt(double x)	sqrt[3](x)	立方根
//n乗根とかは
double pow(double x, double y) //でうまくいっちゃう
pow(10000, 1.0/4.0) //10  4乗根

距離とかもいちいち実装しなくてよくて、

double hypot(double x, double y)	//sqrt(x^2 + y^2)と同じ。

角度を求める

範囲は[-π, +π]
ans = atan2(y, x);  //
y = 1.0 x = 7.0   ans = 0.14...   //横長の三角形
もしくは、
double angle = hypot(x, y)/ y;  でも大丈夫だよ。

素数の求め方．（エラトステネスのふるいで)

//訳あってsetで組んだ。vectorでもほとんどソースコードは変わらない。
set getprime(int num) {
  set prime;  //ans
  set::iterator it;
  for(int i = 2; i <= num; i++) {  //i = 2のときは別々にかんがえて、i = 3; i <= num; i += 2のほうがいいかも．
    bool flag = true;
//終了条件をit != prime.end()のみにすると、無駄な計算が増えるので、結構遅くなる．
    for(it = prime.begin(); (*it)*(*it) <= i && it != prime.end(); it++) {
      if(i % *it == 0) {
	flag = false; break; 
      }
    }
    if(flag) {
      prime.insert(i);
    }
  }
  return prime;
}

vector版
vector getPrime(int num) {
	vector prime;
	int sz = 0;
	for(int i = 2; i <= num; i++) {
		bool flag = true;
		for(int j = 0; j < sz; j++) {
			if(i % prime[j] == 0) {
				flag = false;
				break;
			}
		}
		if(flag) {
			prime.push_back(i); sz++;
		}
	}
	return prime;
}

配列版

    memset(prime, true, sizeof prime);
    for(int i = 2; i < MAX/2; i++) {
      prime[2*i] = false;
    }
    for(int i = 3; i < MAX; i+=2) {
      if(prime[i] == true) {
	for(int j = 2; j < MAX/i; j++) {
	  prime[j*i] = false;
	}
      }
    }

逆ポーランド記法

//54*(((9 + 8) * (4 * 6)) + 7)
//54 9 8 + 4 6 * * 7 + *
みたいに変換。

//動作未確認
	string str;
	char ch;
	Stack acc;
	while(str >> ch) {
		int x = 0;
		while(ch >= '0' && ch <= '9') {
			x = 10*x + (c-'0'); str >> ch;
		}
		if (ch < '0' || ch > '9') {
			int first = acc.top(); acc.pop();
			int second = acc.top(); acc.pop();
			if(ch == '+') x = first + second;
			else if(ch == '*') x = first * second;
		}
		acc.push(x);
	}
	cout << acc.top() << endl;
}

ファレイ配列

i = 1::0/1 1/1
i = 2::0/1 1/2 1/1
i = 3::0/1 1/3 1/2 2/3 1/1
みたいな約分された分数を昇順に並べたときの数列をファレイ配列という．
アルゴリズムサイエンス：入り口からの超入門で存在を知った．
連続する二つの分数
y[k]/x[k]     y[k+1]/x[k+1]
について、x[k]+x[k+1] = i+1が成り立つ時
(y[k]+y[k+1])/(x[k]+x[k+1])を間に挿入することでできる．

typedef pair pii;
const int N = 5;
vector ans;
void farey(int nume0, int deno0, int nume1, int deno1, int nume2, int deno2) {
  if(deno0 + deno1 < N) {
    farey(nume0, deno0, nume0+nume1, deno0+deno1, nume1, deno1);
  }
  ans.push_back(pii(nume1, deno1));
  if(deno1 + deno2 < N) {
    farey(nume1, deno1, nume1+nume2, deno1+deno2, nume2, deno2);
  }
}

閏年か判定

bool isleap(int year) {
  return (year % 4 == 0 && year % 100 != 0) || year % 400 == 0;
}

素因数分解したときの個数を求める

int cnt = 0;
while(1) {
  if(num % 2 == 0) {
    num /= 2; cnt++;
  } else {
    break;
}
int k = 3;
while(1) {
  if(num == 1) break;
  if(num % k == 0) {
    num /= k; cnt++;
  } else { k++ }
}