题解 | #将真分数分解为埃及分数#

#include <stdio.h>
#include <string.h>
//学习一种分解方式吧,主要还是ab互质后分解
//b=a*q+r然后上下同乘q+1 拆出1/q+1来
int gcd(int a, int b);

int main()
{
  int a, b;
  while (scanf("%d/%d", &a, &b) != EOF)
  {
    int under[b];
    int top = -1;
    int q, r, div;

    div = gcd(a, b);
    a /= div, b /= div;
    if (a == 1)
    {
      under[++top] = b;
    }
    else
    {

      while (a != 1)
      {
        q = b / a, r = b % a;
        under[++top] = q + 1;
        a = a - r;
        b = b * (q + 1);
        div = gcd(a, b);
        a /= div, b /= div;
      }

under[++top] = b;

    }

    for (int i = 0; i <= top; i++)
    {
      if (i != 0)
        printf("+");
      printf("1/%d", under[i]);
    }
    printf("\n");
  }
  return 0;
}

int gcd(int a, int b)
{
  int t;
  while (b != 0)
  {
    t = a % b;
    a = b;
    b = t;
  }
  return a;
}