题目描述

给定两个正整数A，B，请你计算 A / B的商和余数。

样例

输入样例：
7
2
输出样例：
3
1

算法1

• 将这里的代码换成c语言写

• 发现通过率9/10, 最后一个大数据过不了. 原因是给C分配的空间不够.

• int C = (int)malloc(sizeof(int) * N); , N只是10000，然而最多分配10^8个依然不能通过hhh

• 超过10^8个会报 float point exception.

• 注：由于方法名叫”div”会冲突，所以写成了”mdiv”

C 代码

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#define N 100010  // 为了读取大整数A

char a[N]; 
int b;

// 计算字符串长度
int getLen(char* c)
{
    int len = 0;
    while(c[len]) len++;
    return len;
}

// 翻转
void reverse(int* arr, int l, int r)
{
    for(int i = l; i <= (l+r) / 2; ++ i)
    {
        int tmp = arr[i];
        arr[i] = arr[r - i + l];
        arr[r - i + l] = tmp;
    }
}

// C是商, idx是商的位数, r是余数, n是A的位数
int* mdiv(int* A, int n, int b, int* r, int* idx)
{
    *r = 0;
    *idx = 0;
    int* C = (int*)malloc(sizeof(int) * N);  

    for(int i = n - 1; i >= 0; i -- )
    {
        *r = (*r) * 10 + A[i];
        C[*idx] = *r / b;
        *idx = *idx + 1;
        *r = *r % b;
    }

    reverse(C, 0, (*idx) - 1);
    while(*idx > 1 && C[*idx - 1] == 0) (*idx) --;
    return C;
}

int main()
{
    gets(a);
    scanf("%d", &b);
    int n = getLen(a);

    int* A = (int*)malloc(sizeof(int) * N);
    for(int i = n - 1, j = 0; i >= 0; i --, j ++ ) A[j] = a[i] - '0';

    int r = 0;
    int idx = 0;
    int* res = mdiv(A, n, b, &r, &idx);  

    for(int i = idx - 1; i >= 0; i -- ) printf("%d", res[i]);
    printf("\n%d", r);

    return 0;
}

算法2（优化算法1）

• 针对算法1，究其本质，人家c++的vector怎么就这么好用呢。因此，决定在算法1基础上，去解决最后一个大数据的问题。

• 发现到一点，“前导0”只存在一开始的时候，因此我们一开始就存了一些没有用的0到C里面.

• 所以，我们不要把前导0存进去,大数据A长度是100000，做了除法之后长度应该是比100000更短才对.

• 只需要修改mdiv方法就ok了.

C 代码

#include<stdlib.h>
#include<string.h>
#include<stdio.h>

#define N 100010

char a[N];
int b;

int getLen(char* c)
{
    int len = 0;
    while(c[len]) len++;
    return len;
}

// 翻转
void reverse(int* arr, int l, int r)
{
    for(int i = l; i <= (l+r) / 2; ++ i)
    {
        int tmp = arr[i];
        arr[i] = arr[r - i + l];
        arr[r - i + l] = tmp;
    }
}

// C是商, r 是余数, idx是商的位数,n是A的位数
int* mdiv(int* A, int n, int b, int* r, int* idx)
{
    *r = 0;
    *idx = 0;
    int* C = (int*)malloc(sizeof(int) * N);  

    int flag = 0;
    for(int i = n - 1; i >= 0; i -- ) {
        *r = (*r) * 10 + A[i];
        C[*idx] = *r / b;

        if(!flag && C[*idx] == 0){
            // 最开始的前导0,不添加进去.不作处理.
        }else{
            flag = 1;
            *idx = *idx + 1;    
        }

        *r = *r % b;
    }

    reverse(C, 0, (*idx) - 1);
    return C;
}

int main()
{
    gets(a);
    scanf("%d", &b);
    int n = getLen(a);

    int* A = (int*)malloc(sizeof(int) * N);
    for(int i = n - 1, j = 0; i >= 0; i --, j ++ ) A[j] = a[i] - '0';

    int r = 0;
    int idx = 0;
    int* res = mdiv(A, n, b, &r, &idx);  

    for(int i = idx - 1; i >= 0; i -- ) printf("%d", res[i]);
    printf("\n%d", r);
}