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 まで 〜

https://qiita.com/drken/items/7c6ff2aa4d8fce1c9361#stdbitset-%E3%82%92%E7%94%A8%E3%81%84%E3%81%9F%E5%87%BA%E5%8A%9B

 

・ベクトルの要素検索

std::findでvector<int> vを検索

find(v.begin(), v.end(), i) でindexを返す

find(v.begin(), v.end(), i) == v.end() で存在するか判定