处理用 C 编写的大量代码片段

Question

我写了这个代码片段作为一个问题的解决方案，但是在一个尝试大数字作为输入的测试用例中（例如 10000000000 10000000000 1），一个奇怪的输出来自 out.it 对整数范围的工作数字，但我该如何处理大数字的代码？

这是条件：(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;
}

可以看到问题了here

ps 1：我的编译器是GNU GCC 5.1.0.

ps 2：我是提交给网站编译的所以不能安装任何国外库

Answer 1

假设您的编译器将 int 定义为具有 32 位存储，那么您可以处理最多 2^31-1.

的正数

如果您需要更进一步，例如最多 2^64-1，请考虑使用可以处理更大整数的（可能是无符号的）类型——例如，如果您有 C11，请参见 Fixed width integer types。

如果你需要无界整数，那么问题就复杂多了。在这种情况下，您可以做的最简单的事情就是使用库，例如像 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.

Answer 2

如果您的数字大于 64 位，则必须使用像 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 这样的 bignum 库。

您的代码的第一部分如下所示：

#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;
}

Answer 3

使用 long long 数据类型代替 int。因为一个带符号的 32 位整数最多可以处理 2^31 - 1（即 32,767），而 unsigned int 最多可以处理 65,535。

此外，即使整数在 int 范围内，您也应该在 codeforces 的竞赛中使用 long long 以防乘法。请参阅示例以获得更好的解释。

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

阅读更多关于 Data Type Ranges

如果您愿意，可以减少代码长度，例如：

#include<stdio.h>
int main()
{
    long long m, n, a, count1 = 1, count2 = 1;
    scanf("%lld%lld%lld",&m,&n,&a);
    count1 *= (m/a);
    count2 *= (n/a);
    if (m%a != 0) count1++;
    if (n%a != 0) count2++;
    printf("%lld", count1*count2);
    return 0;
}

处理用 C 编写的大量代码片段

handle snippet code wrtten in C for large numbers

c

gcc

biginteger

bignum