UVA 10976 分数拆分【暴力】

题目链接：https://vjudge.net/contest/210334#problem/C

题目大意：

It is easy to see that for every fraction in the form 1 k (k > 0), we can always find two positive integers x and y, x ≥ y, such that: 1 k = 1 x + 1 y Now our question is: can you write a program that counts how many such pairs of x and y there are for any given k?

Input

Input contains no more than 100 lines, each giving a value of k (0 < k ≤ 10000).

Output

For each k, output the number of corresponding (x, y) pairs, followed by a sorted list of the values of x and y, as shown in the sample output.

Sample Input 2 12

Sample Output

1/2 = 1/6 + 1/3

1/2 = 1/4 + 1/4

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

解题思路：

这个题显然要用暴力求解，但是暴力的最大数量是可以计算的，题目规定x≥y,所以y的最大值应该为k的2倍，确定范围之后对y开始枚举就可以了。

当然，这个题由于精度问题，我们还是尽量避免除法运算，首先把式子通分，可以求得x = [k * y / (y - k)], 这里要求y必须大于k,所以枚举时y的范围可以进一步缩小为[k+1, 2*k]。所以，我们可以这样想，对y进行枚举，判断k*y%(y - k)这个式子是否为零，如果为零，说明此时算出的x为正整数，而这个x也正是符合题意的x。

#include <iostream>
#include <stdio.h>
using namespace std;
#define NUM 1005

int main()
{
    int i, j,n;
    while (cin>>n)
    {
        int a[NUM], b[NUM];
        ;
        ; y <=  * n; y++)            //i代表的是y的数值,至于y的为什么是这样范围，自己仔细分析便可知
        {
            )       //用%判断(y*n)是否能被(y+n)整除，这样计算的x是否满足条件
            {
                x = (y*n) / (y - n);      //因为y的范围小，且好确定，所以选择遍历y，x的值则通过简单的数学变换得到
                a[cur] = x;
                b[cur] = y;
                cur++;                   //开始因为上面写成a[cur++];b[cur++]wrong了很久
            }
        }
        cout << cur << endl;
        ; i < cur; i++)
        {
            printf("1/%d = 1/%d + 1/%d\n", cur, a[i], b[i]);
        }
    }
    ;
}

2018-04-11

秒客网

UVA 10976 分数拆分【暴力】

相关文章