Atcoderの解説に出てくる式に度々詰まるのでメモ

詳しく教えてくれてるサイト

除数を3とし、被除数1〜5まで考えてみる

1/3= 1/3
2/3= 2/3
3/3= 1
4/3= 1+1/3
5/3= 1+2/3

小数点以下のうち一番小さいのは1/3 つまり1/除数

1-(1/除数)=(除数-1)/除数を足して、繰り上げてから切り捨てることで、整数の切り上げができる。

c++

int a; //被除数
int b; //除数
int ans //計算結果

ans = a/b +(b-1)/b

式を整理して

c++

int a; //被除数
int b; //除数
int ans //計算結果

ans = (a + b - 1 ) / b;

int : 2^31-1
long long : 2^63-1