暴力枚举 UVA 10976 Fractions Again?!

时间：2021-11-18 17:59:09

题目传送门

 /*

     x>=y, 1/x <= 1/y, 因此1/k - 1/y <= 1/y, 即y <= 2*k

 */

 #include <cstdio>

 #include <iostream>

 #include <algorithm>

 #include <cmath>

 #include <cstring>

 #include <string>

 #include <map>

 #include <set>

 #include <queue>

 using namespace std;

 const int MAXN  = 1e4 + ;

 const int INF = 0x3f3f3f3f;

 struct NODE

 {

     int x, y;

 }node[MAXN];

 int main(void)        //UVA 10976 Fractions Again?!

 {

     //freopen ("UVA_10976.in", "r", stdin);

     int k;

     while (scanf ("%d", &k) == )

     {

         int cnt = ;

         for (int i=k+; i<=*k; ++i)

         {

             if ((i*k) % (i-k) == )

             {

                 node[++cnt].x = (i*k) / (i-k);

                 node[cnt].y = i;

             }

         }

         printf ("%d\n", cnt);

         for (int i=; i<=cnt; ++i)

         {

             printf ("1/%d = 1/%d + 1/%d\n", k, node[i].x, node[i].y);

         }

     }

     return ;

 }

 /*

 2

 1/2 = 1/6 + 1/3

 1/2 = 1/4 + 1/4

 8

 1/12 = 1/156 + 1/13

 1/12 = 1/84 + 1/14

 1/12 = 1/60 + 1/15

 1/12 = 1/48 + 1/16

 1/12 = 1/36 + 1/18

 1/12 = 1/30 + 1/20

 1/12 = 1/28 + 1/21

 1/12 = 1/24 + 1/24

 */

相关文章