What I noticed is that ‘**long long int**’ can store only 9 digit numbers in the C/C++ compiler in codechef. So when I want to calculate, say

**(a.b)mod c**

and, ‘**a**’ and ‘**b**’ are quite large (say 10^9+5) and c=10^9+7, then (a.b) is pretty large and an overflow occurs. Therefore, when I try to do a ‘**mod c**’ of the result, a negative value appears.

So, how do I find **(a.b)mod c** in constant time?

In fact I’m not C/C++ guru, but `int`

is up to 2 * 10^9 and `long long`

twice bigger, so it can hold positive integer up to 4 * 10^18

I’m always lost in so many times that are in C/C++ has, but for contest programming I’m using just `char`

, `int`

and `long long`

(sometimes I add `unsigned`

modifier to those).

Maybe someone more experienced in C/C++ can specify the difference between `int`

, `long int`

, `long long int`

, `long`

and `long long`

.

So you can use `long long`

on CodeChef. But you have to be aware that

```
long long res;
int a = 1000*1000*1000;
int b = 1000*1000*1000;
res = a * b;
```

won’t work, because `a * b`

is calculated as `int`

and then stored in `long long`

variable to prevent this you can:

- change type of a or b to long long (I’m using this) or
- cast the variable in calculation
`((long long)a)*b`

- on my PC also
`long(a) * b`

is working, but I do not know how to use it with`long long`

long long int can hold upto 18 digits, your understanding is wrong regarding that.

And

```
(a*b)%c = ((a%c)*(b%c))%c
```

This will keep the values stored in a and b not to overflow.

According to the C standard,

```
int -32767 to +32767 representable in 16 bits
long -2147483647 to +2147483647 representable in 32 bits
long long -9223372036854775807 to +9223372036854775807 representable in 64 bits
```

if a and b are both `long long`

s (or as described in question `long long int`

s)

short is (signed) short int.

long is (signed) long int.

long long is (signed) long long int.

@betlista >> in case of long long / long long int you add “LL” while assigning. For example, look at this code http://www.codechef.com/viewsolution/1721303

@bugkiller its for representation that the number is long long … for example if we say a=25L its just represting long type integer … hope it helps

@bugkiller LL - yes, but you can add LL only to constants not to variables, even `int a = 0LL`

won’t work

are you sure about the boundaries of the types, AFAIK int is typically 4 bytes long, same as pointer…

That dude. Seems that I was wrong :).

That helped. Thanks!

@betlista >> Yeah, you are right, *mostly* int is 4 bytes. However, still if you want specific size, then Standard Integer Types by C99 states:

```
int8_t
uint8_t
int32_t
uint32_t
```

etc. The form is (u)intX_t where ‘u’ specifies that you want an unsigned quantity and X is the number of bits.

```
printf("sizeof(int) = %d\nsizeof(long int) = %d\nsizeof(long long int = %d\n", sizeof(int), sizeof(long int), sizeof(long long int));
```

prints

```
sizeof(int) = 4
sizeof(long int) = 4
sizeof(long long int = 8
```

A simple reason that int is *mostly* 4 bytes might be that suppose there is a 32 bit machine and you want to store a 16 bit int then it will mask off the unused bits, and will opearate in 32 bits and convert the answer to 16 bits. Just a guess

The size of

```
int
```

is compiler (or implementation) dependent. Each target machine will be some x-bit machine. And there, size of an

```
int
```

will be exactly x bits. The reason is, out of all the integer types,

```
int
```

must be the most efficient one. The only other guarantee about sizes is

```
sizeof(short int) <= sizeof(int) <= sizeof(long int)
```

.

PS: I have read this somewhere, long back. I do not know any more on this, Just thought, I would share this too.

long long int can store upto 10^18.

and(a.b)mod c=((a%c).(b%c))%c;

and hence if c<10^9+1,this equation can be easily used to find the mod of (a.b)%c .if c>10^9+1 there is a chance of overflow.