 # What is (a.b)mod c?

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`
2 Likes

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``````
1 Like

@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.

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.

1 Like

@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!