【PTA-C语言】7-35 有理数均值 测试点2 运行超时

Question

题目来源

地址：https://pintia.cn/problem-sets/14/exam/problems/815

错误信息

代码内容

#include <stdio.h>
int num_zi, num_mu;
void huajian(int* zi, int* mu)
{
    int min;
    if (zi > mu)
    {
        min = *mu;
    }
    else {
        min = *zi;
    }
    int i;
    for (i = 2; i < min + 1; i++)
    {
        if (*zi % i == 0 && *mu % i == 0)
        {
            *zi /= i;
            *mu /= i;
            i--;
        }
    }
}
void jia(int* A1, int* B1, int* A2, int* B2)
{
    huajian(A1, B1), huajian(A2, B2);
    num_mu = *B1 * *B2, num_zi = *B2 * *A1 + *B1 * *A2;
    huajian(&num_zi, &num_mu);
}
int main()
{
    int n;
    int a1, b1, a2, b2;
    scanf("%d", &n);
    scanf("%d/%d", &a1, &b1);
    if (n == 1)
    {
        huajian(&a1, &b1);
        if (b1 == 1)
        {
            printf("%d", a1);
        }
        else {
            printf("%d/%d", a1, b1);
        }
    }
    else {
        int i;
        for (i = 0; i < n - 1; i++)
        {
            scanf("%d/%d", &a2, &b2);
            huajian(&a2, &b2);
            jia(&a1, &b1, &a2, &b2);
            a1 = num_zi, b1 = num_mu;
        }
        num_mu *= n;
        huajian(&num_zi, &num_mu);
        if (num_mu == 1)
        {
            printf("%d", num_zi);
        }
        else if (num_zi == 0)
        {
            printf("0");
        }
        else {
            printf("%d/%d", num_zi, num_mu);
        }
    }
    return 0;
}

备注
代码里是随时化简，为什么还是会溢出？是因为huajian函数运行时间太长吗？求找出问题所在，非常感谢。

Answer 1

是的，化简时间太长了，求最大公约数的方法可以改进一下
修改如下：

#include <stdio.h>
int num_zi, num_mu;
int gcd(int a, int b) {
    if (b % a == 0)
        return a;
    gcd(b, a%b);
}
void huajian(int* zi, int* mu)
{
    if(*zi==0||*mu==0||*zi==1||*mu==1)
        return;
    int x = gcd(*zi, *mu);
    *zi /= x;
    *mu /= x;
}
void jia(int* A1, int* B1, int* A2, int* B2)
{
    huajian(A1, B1), huajian(A2, B2);
    num_mu = *B1 * *B2, num_zi = *B2 * *A1 + *B1 * *A2;
    huajian(&num_zi, &num_mu);
}
int main()
{
    int n;
    int a1, b1, a2, b2;
    scanf("%d", &n);
    scanf("%d/%d", &a1, &b1);
    if (n == 1)
    {
        huajian(&a1, &b1);
        if (b1 == 1)
        {
            printf("%d", a1);
        }
        else {
            printf("%d/%d", a1, b1);
        }
    }
    else {
        int i;
        for (i = 0; i < n - 1; i++)
        {
            scanf("%d/%d", &a2, &b2);
            huajian(&a2, &b2);
            jia(&a1, &b1, &a2, &b2);
            a1 = num_zi, b1 = num_mu;
        }
        num_mu *= n;
        huajian(&num_zi, &num_mu);
        if (num_mu == 1)
        {
            printf("%d", num_zi);
        }
        else if (num_zi == 0)
        {
            printf("0");
        }
        else {
            printf("%d/%d", num_zi, num_mu);
        }
    }
    return 0;
}