# Untitled

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);
}```