handle snippet code wrtten in C for large numbers

Question

I wrote this snippet code as a solution for a problem but in a test case that tries big numbers as input(for example 10000000000 10000000000 1), a weird output comes out.it's work for integer range number but how can I handle code for big numbers?

here's the condition: (1 ≤ n, m, a ≤ 10^9).

#include<stdio.h>

int main()
{
    int m, n, a;
    int count = 1;

    scanf("%d%d%d",&m,&n,&a);

    if (m%a != 0) {
        count *= ((m/a)+1);
    }
    else {
        count *= (m/a);
    }

    if (n%a != 0) {
        count *= ((n/a)+1);
    } else {
        count *= (n/a);
    }

    printf("%d",count);

    return 0;
}

you can see the problem here

ps 1: my compiler is GNU GCC 5.1.0.

ps 2: I submit it to website compiler so can't install any foreign library.

How big do you need to go? The problem is likely that you're overflowing 32-bit ints for m, n and a. Would 64-bit values do (you have a long long already here!), or do you need arbitrarily large numbers? — Rup, Mar 27 '18 at 23:48
Possible duplicate of [What is the simplest way of implementing bigint in C?](https://stackoverflow.com/questions/3340511/what-is-the-simplest-way-of-implementing-bigint-in-c) — Ken White, Mar 27 '18 at 23:49
you might need to use `scanf("%lld%lld%lld",&m,&n,&a);` when you change the definition of your variables to `long long int m, n, a;` — bruceg, Mar 27 '18 at 23:57

score 2 · Answer 1 · answered Mar 28 '18 at 00:10

If your numbers are bigger than 64 bits, you will have to use a bignum library like GMP. On Debian-based Linux systems, you can install with sudo apt-get install libgmp3-dev. Then, just include gmp.h and read up on the docs.

The first portion of your code would look like this:

#include <stdio.h>
#include <gmp.h>

int main(void) {
    mpz_t m, n, a;
    mpz_init(m); //allocate memory for the mpz_t
    mpz_init(n);
    mpz_init(a);

    mpz_inp_str(m, stdin, 10); //variable, input stream, base
    mpz_inp_str(n, stdin, 10);
    mpz_inp_str(a, stdin, 10);

    mpz_t count;
    mpz_init_set_ui(count, 1); //count = 1

    mpz_t result;
    mpz_init(result);

    mpz_mod(result, m, a); //result = m % a
    if(mpz_cmp(result, 0) != 0) { //result == 0
        mpz_tdiv_q(result, m, a); //integer truncated division: result = m / a
        mpz_add_ui(result, result, 1); // result += 1;
        mpz_mul(count, count, result); // count *= result;
    }

    //the rest of the code 

    mpz_clear(m); //clean up
    mpz_clear(n);
    mpz_clear(a);
    mpz_clear(count);
    mpz_clear(result);

    return 0;
}

Acorn · Answer 2 · 2018-03-28T12:35:08.423

Assuming your compiler defines int as having 32-bit storage, then you can handle positive numbers up to 2^31-1.

If you need to go further, e.g. up to 2^64-1, consider using a (possibly unsigned) type that can handle bigger integers -- see for instance the Fixed width integer types if you have C11.

If you need unbounded integers, then the problem is much more complex. The easiest you can do in this case is use a library, e.g. like the GNU multiple precision arithmetic library:

GMP is a free library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating-point numbers. There is no practical limit to the precision except the ones implied by the available memory in the machine GMP runs on. GMP has a rich set of functions, and the functions have a regular interface.

the problem is if I define my count variable as long long int , the output for the small numbers will be wrong. — oldMCdonald, Mar 28 '18 at 00:04
It shouldn't be wrong? There's no reason a 64-bit variable can't work with smaller numbers. — Rup, Mar 28 '18 at 10:38

Ishpreet · Accepted Answer · 2018-03-28T12:12:30.130

Use long long data type instead of int. Because a signed 32-bit integer can handle upto 2^31 - 1(i.e 32,767) and unsigned int can reach upto 65,535.

Also even if the integers are within int range you should use long long in contests on codeforces in case of multiplication. See example for better explanation.

Example:

m: 100000
n: 100000
a: 1
count = 1

From your code,
count *= m/a; // count *= 100000/1 = 100000
Now,
count *= n/a; // count *= 100000/1 = 10000000000(10^10);
10^10 is beyond 32 bit int range so you will get a wrong answer -_-
So use long long to avoid such overflow errors

handle snippet code wrtten in C for large numbers

3 Answers3