This is my first time actually trying to contribute something, so please go easy on me....

Hello Codeforces! After a long time of search for a cure for precision errors in C++ while dealing with just integers, I was motivated to write a blog for a curated collection of one. Sure some common ones do already exist in the previous blogs, some really cool ones can be found while browsing other programmers' templates, but why not have a blog which saves the time of search and makes it easier for CP Enthusiasts to improve?

I have implemented a few as follows (may include the common ones):

1) ceil(a/b) and floor(a/b): Handling negative division as well...

```
ll divceil(ll a,ll b){ return a/b+(a%b>0);}
ll divfloor(ll a,ll b){ return a/b-(a%b<0);}
```

2) power(a,b):

```
ll binpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res*=a;
a*=a,b>>=1;
}
return res;
}
```

3) Floor(logb(x)):

```
ll lg(ll x,ll b=2){
if(b==1) return -1; //Modify this as per need
if(b==2) return 63-__builtin_clzll(x); //O(1) for log2
ll p=1,ans=0;
while(true){
if(p>x) return ans-1;
if(p>LLONG_MAX/b) return ans;
p*=b,ans++;
}
}
```

4) nth-root (general): Thanks to LeoPro for the trick to deal with overflows

```
const ll INF = LLONG_MAX // You may change ll to ull and LLONG_MAX to ULLONG_MAX
ll mult(ll a,ll b){
if(b==0) return 0;
return a>INF/b?INF:a*b;
}
ll binpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=mult(res,a);
a=mult(a,a),b>>=1;
}
return res;
}
ll bin_nth_rt(ll x,ll n){
if(x==1||n==1) return x;
if(x==INF) x--; // Doesn't make a difference in answer, and check function fails for INF
ll l=0,r=x,m;
while(r-l>1){
m=l+(r-l)/2;
if(binpow(m,n)>x) r=m;
else l=m;
}
return l;
}
```

Please feel free to highlight any errors, or areas with room for improvement in performance, handling overflows, divide by zero, etc and contributing your own in the comments.

Thanks for reading!

**UPD**: Changed divfloor and divceil according to bicsi 's idea.

**UPD**: nth-root has now been updated to handle entire integer range.

niceee

thanks

To handle overflows you can perform the following check to multiply two integers:

It is nice to encapsulate this into a function (if you want to use it more than once) alike

Note that it is allowed to call

`mult`

on already overflowed values, the result still is INF. For example,`mult(mult(1e15, 1e15), 42)`

is fine.P. S. This only works for positive integers. For possible negatives you can just replace checks with

`abs(a) >= INF / abs(b)`

and case`b == 0`

requires additional care...Thanks a lot... I'll include this in the blog

Just wanted to ask, is the equality really necessary?

This is because if we want to perform

`mult(1,9e18)`

, where`INF`

is`LLONG_MAX`

, it will not return`9e18`

, but`LLONG_MAX`

.Yes, sometimes it returns

`INF`

instead of a value, that is just slightly less than`INF`

, but it is usually unimportant in competitive programming: either you can prove, that there could occur no overflow, or you want to know, whether the number is less than`1e18`

, or not.In fact, your version is indeed correct, but it wasn't obvious for me, and better safe than sorry. I guess I have somewhere seen a blog about that, but can't find it now, so here's a quick proof, in case anyone wants:

Bad case is $$$ab > INF \iff a > \frac{INF}{b}$$$ and an integer is greater than a floating point number iff it's greater than its rounding down. Therefore, $$$a > \frac{INF}{b} \iff a > \lfloor\frac{INF}{b}\rfloor$$$.

Cool thanks

__int128_t

For divfloor, I usually just do

`a/b - (a%b<0)`

and for divceil`a/b + (a%b>0)`

. It’s usually the fastest, as most architectures do division and modulo at the same time anyways, and compilers know to optimize this pattern.Added :)

Doesn't the code for floor(logb(x)) cause an infinite loop?

Thanks for pointing out... Fixed

thanks so much