Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
8.8 kB
0
Indexable
Never
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

long long *prime_factoriztion(long long num_a, long long num_b, long long count_a, long long count_b)
{
    long long i, j, k, isPrime;
    long long prime_factors[count_a * 2 + count_b * 2 + 1];
    long long prime_count = 1;
    long long prime_locate = 0;
    long long *ptr_prime_factors = prime_factors;

    /* Find all Prime factors */
    for (i = 2; i <= num_a; i++)
    {
        /* Check 'i' for factor of num */
        if (num_a % i == 0)
        {
            /* Check 'i' for Prime */
            isPrime = 1;
            for (j = 2; j <= i / 2; j++)
            {
                if (i % j == 0)
                {
                    isPrime = 0;
                    break;
                }
            }

            /* If 'i' is Prime number and factor of num */
            if (isPrime == 1)
            {
                prime_factors[prime_locate] = i;
                // printf("prime_factors[%lld] = %lld\n", prime_locate, i);
                prime_locate++;
                k = num_a / i;
                while (k % i == 0)
                {
                    k = k / i;
                    prime_count++;
                }
                prime_factors[prime_locate] = prime_count;
                // printf("prime_factors[%lld] = %lld\n", prime_locate, prime_count);
                prime_count = 1;
                prime_locate++;
            }
        }
    }

    /* Find all Prime factors */
    for (i = 2; i <= num_b; i++)
    {
        /* Check 'i' for factor of num */
        if (num_b % i == 0)
        {
            /* Check 'i' for Prime */
            isPrime = 1;
            for (j = 2; j <= i / 2; j++)
            {
                if (i % j == 0)
                {
                    isPrime = 0;
                    break;
                }
            }

            /* If 'i' is Prime number and factor of num */
            if (isPrime == 1)
            {
                prime_factors[prime_locate] = i;
                // printf("prime_factors[%lld] = %lld\n", prime_locate, i);
                prime_locate++;
                k = num_b / i;
                while (k % i == 0)
                {
                    k = k / i;
                    prime_count++;
                }
                prime_factors[prime_locate] = prime_count;
                // printf("prime_factors[%lld] = %lld\n", prime_locate, prime_count);
                prime_count = 1;
                prime_locate++;
            }
        }
    }

    return ptr_prime_factors;
}

long long prime_count(long long num)
{
    long long i, j, isPrime;
    long long count = 0;

    /* Find all Prime factors */
    for (i = 2; i <= num; i++)
    {
        /* Check 'i' for factor of num */
        if (num % i == 0)
        {
            /* Check 'i' for Prime */
            isPrime = 1;
            for (j = 2; j <= i / 2; j++)
            {
                if (i % j == 0)
                {
                    isPrime = 0;
                    break;
                }
            }

            /* If 'i' is Prime number and factor of num */
            if (isPrime == 1)
            {
                count++;
            }
        }
    }
    if (num == 1)
    {
        count = 0;
    }

    return count;
}

long long lcm(long long a, long long b)
{
    long long i, j, k;
    long long prime_a = prime_count(a);
    long long prime_b = prime_count(b);
    long long *prime_factors;
    long long prime_num_a[prime_a];
    long long prime_num_b[prime_b];
    long long prime_count_a[prime_a];
    long long prime_count_b[prime_b];
    long long check = 0;

    if (prime_a == 0)
    {
        return b;
    }
    else if (prime_b == 0)
    {
        return a;
    }

    prime_factors = prime_factoriztion(a, b, prime_a, prime_b);

    for (i = 0; i < prime_a; i++)
    {
        prime_num_a[i] = prime_factors[i * 2];
        prime_count_a[i] = prime_factors[i * 2 + 1];
    }
    for (i = 0; i < prime_b; i++)
    {
        prime_num_b[i] = prime_factors[(prime_a + i) * 2];
        prime_count_b[i] = prime_factors[(prime_a + i) * 2 + 1];
    }

    /* Check right place */
    // for (i = 0; i < prime_a; i++)
    // {
    //     printf("prime_num_a[%lld] = %lld\n", i, prime_num_a[i]);
    //     printf("prime_count_a[%lld] = %lld\n", i, prime_count_a[i]);
    // }
    // for (i = 0; i < prime_b; i++)
    // {
    //     printf("prime_num_b[%lld] = %lld\n", i, prime_num_b[i]);
    //     printf("prime_count_b[%lld] = %lld\n", i, prime_count_b[i]);
    // }

    /* Find LCM */
    long long lcm = 1;
    for (i = 0; i < prime_a; i++)
    {
        check = 0;
        for (j = 0; j < prime_b; j++)
        {
            if (prime_num_a[i] == prime_num_b[j])
            {
                if (prime_count_a[i] > prime_count_b[j])
                {
                    for (k = 0; k < prime_count_a[i]; k++)
                    {
                        lcm = lcm * prime_num_a[i];
                    }
                }
                else
                {
                    for (k = 0; k < prime_count_b[j]; k++)
                    {
                        lcm = lcm * prime_num_b[j];
                    }
                }
                break;
            }
            else
            {
                check++;
            }
            if (check == prime_b)
            {
                for (k = 0; k < prime_count_a[i]; k++)
                {
                    lcm = lcm * prime_num_a[i];
                }
            }
        }
    }

    for (i = 0; i < prime_b; i++)
    {
        check = 0;
        for (j = 0; j < prime_a; j++)
        {
            if (prime_num_b[i] == prime_num_a[j])
            {
                break;
            }
            else
            {
                check++;
            }
            if (check == prime_a)
            {
                for (k = 0; k < prime_count_b[i]; k++)
                {
                    lcm = lcm * prime_num_b[i];
                }
            }
        }
    }

    return lcm;
}

long long gcd(long long a, long long b)
{
    long long i, j, k;
    long long prime_a = prime_count(a);
    long long prime_b = prime_count(b);
    long long *prime_factors;
    long long prime_num_a[prime_a];
    long long prime_num_b[prime_b];
    long long prime_count_a[prime_a];
    long long prime_count_b[prime_b];

    if (a % b == 0)
    {
        return b;
    }

    if (prime_a == 0)
    {
        return 1;
    }
    else if (prime_b == 0)
    {
        return 1;
    }

    prime_factors = prime_factoriztion(a, b, prime_a, prime_b);

    for (i = 0; i < prime_a; i++)
    {
        prime_num_a[i] = prime_factors[i * 2];
        prime_count_a[i] = prime_factors[i * 2 + 1];
    }
    for (i = 0; i < prime_b; i++)
    {
        prime_num_b[i] = prime_factors[(prime_a + i) * 2];
        prime_count_b[i] = prime_factors[(prime_a + i) * 2 + 1];
    }

    /* Check right place */
    // for (i = 0; i < prime_a; i++)
    // {
    //     printf("prime_num_a[%lld] = %lld\n", i, prime_num_a[i]);
    //     printf("prime_count_a[%lld] = %lld\n", i, prime_count_a[i]);
    // }
    // for (i = 0; i < prime_b; i++)
    // {
    //     printf("prime_num_b[%lld] = %lld\n", i, prime_num_b[i]);
    //     printf("prime_count_b[%lld] = %lld\n", i, prime_count_b[i]);
    // }

    /* Find GCD */
    long long gcd = 1;
    for (i = 0; i < prime_a; i++)
    {
        for (j = 0; j < prime_b; j++)
        {
            if (prime_num_a[i] == prime_num_b[j])
            {
                if (prime_count_a[i] < prime_count_b[j])
                {
                    for (k = 0; k < prime_count_a[i]; k++)
                    {
                        gcd = gcd * prime_num_a[i];
                    }
                }
                else
                {
                    for (k = 0; k < prime_count_b[j]; k++)
                    {
                        gcd = gcd * prime_num_b[j];
                    }
                }
                break;
            }
        }
    }

    return gcd;
}

int main(void)
{
    long long a_1, a_2, b_1, b_2;
    long long gcd_1, gcd_2;
    long long numer, denom;
    long long re_a1, re_a2, re_b1, re_b2;

    scanf("%lld/%lld+%lld/%lld", &a_1, &b_1, &a_2, &b_2);
    gcd_1 = gcd(a_1, b_1);
    gcd_2 = gcd(a_2, b_2);
    re_a1 = a_1 / gcd_1;
    re_b1 = b_1 / gcd_1;
    re_a2 = a_2 / gcd_2;
    re_b2 = b_2 / gcd_2;
    // printf("reduce_a1 = %lld\n", re_a1);
    // printf("reduce_b1 = %lld\n", re_b1);
    // printf("reduce_a2 = %lld\n", re_a2);
    // printf("reduce_b2 = %lld\n", re_b2);

    denom = lcm(re_b1, re_b2);
    numer = re_a1 * (denom / re_b1) + re_a2 * (denom / re_b2);
    // printf("numer = %lld\n", numer);
    // printf("denom = %lld\n", denom);

    printf("%lld/%lld\n", numer, denom);
}