Tips for AtCoder
〇最大公約数の実装
再帰的には
int gcd(int x, int y)
{
return y==0 ? x:gcd(y,x % y);
}
再帰使わないなら
int gcd(int x, int y)
{
int temp;
while (y != 0) {
temp = y;
y = x % y;
x = temp;
}
return (x);
}
・最小公倍数の実装
int lcd(int x, int y){
return (x/gcd(x,y)*y);
}
※x/gcdはint型だから誤差の心配ない、先にgcdで割ることでオーバーフローしにくくする
〇bit演算
not...1と0を入れ替え→~
or...どっちかが1なら1→|
xor...01が一致したら0、一致しなければ1→^
and...両方1なら1→&
シフト→左シフトは<<1 右シフトは>>1
#include <bitset>
#include <iostream>
using namespace std;
int main(){
string s1 = "1100";
bitset<4> b1(s1);
b1 = b1 >> 2;
//"0011"になる
return 0;
}
参考:ビット演算 (bit 演算) の使い方を総特集! 〜 マスクビットから bit DP まで 〜
・ベクトルの要素検索
std::findでvector<int> vを検索
find(v.begin(), v.end(), i) でindexを返す
find(v.begin(), v.end(), i) == v.end() で存在するか判定