UVA 10976 Fractions Again?(枚举+数学)

题目大意:

  就是说输入一个k,然后求出满足1/k = 1/x+1/y的所有形式,使得x>=y。

解题思路:

  拿到这个题后,看到题目仅仅给了x>=y.这个条件,感觉无从下手,但是仔细想想就不难发现,只要我们

首先确定了枚举的范围,那么我们就能够在这个区间内,找到符合我们要求的解了。

推导:

  因为x>=y,所以1/x<=1/y,由1/k-1/x=1/y  -> 1/k-1/y <= 1/y -> y<=2k,

  然后,由等式1/k = 1/x+1/y -> x = (y*k)/(y-k)

  这样一来,我们只需要在[k+1,2k]上枚举y的值,然后找到 (y*k)%(y-k)==0的所有x的值就好了。

代码:

# include<cstdio>
# include<iostream>
# include<algorithm>
# include<functional>
# include<cstring>
# include<string>
# include<cstdlib>
# include<iomanip>
# include<numeric>
# include<cctype>
# include<cmath>
# include<ctime>
# include<queue>
# include<stack>
# include<list>
# include<set>
# include<map>

using namespace std;

const double PI=4.0*atan(1.0);

typedef long long LL;
typedef unsigned long long ULL;

# define inf 999999999
# define MAX 10000

int k;

struct node
{
    int x, y;
}a[MAX];

int main(void)
{
    while ( cin>>k )
    {
        int num = 0;
        for ( int yy = k+1;yy <= 2*k;yy++ )
        {
            int fenzi = yy*k;
            int fenmu = yy-k;
            if ( fenzi%fenmu == 0 )
            {
                int xx = fenzi/fenmu;
                a[num].x = xx;
                a[num++].y = yy;
            }
        }
        cout<<num<<endl;
        for ( int i = 0;i < num;i++ )
        {
            printf("1/%d = 1/%d + 1/%d
",k,a[i].x,a[i].y);
        }
    }



    return 0;
}
View Code
原文地址:https://www.cnblogs.com/wikioibai/p/4391387.html