What is (a.b)mod c?

general
, , ,
1

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?

2

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 :wink:

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
3

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
4

if a and b are both long longs (or as described in question long long ints)

5

short is (signed) short int.
long is (signed) long int.
long long is (signed) long long int.

1 Like
6

@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

7

@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

8

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

9

That dude. Seems that I was wrong :).

10

That helped. Thanks!

11

@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 :slight_smile:

12

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. :slight_smile:

13

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.