hdu 5974 - theflowerofac^MQLYES的专栏 - 博客频道 - CSDN.NET

文章价值(3) ?
阅读数(201) ?

x+y=a , lcm(x,y)=b ? ? ? ?有解 输出x,y

?看了一篇博客 已经写的很清楚了 ?

http://blog.csdn.net/betwater/article/details/53055607

然后就是一个问题想不明白

为什么 i ,j 互质 ?i+j 和i*j 一定互质

在网上找到了证明:

若两个数互质,证明它们的和与它们的积互质

证明:设这两个数为p ,q
M=p+q N=pq
假设M,N不互质,则有:M=aN或 N=aM (a>1且a为自然数)
当M=aN时,
p+q=apq
p= q(ap-1)
p/q=ap-1
因为p,q互质,所以p/q为1或非整数
当p/q=1时,ap=2(不符)
当p/q为非整 数时 ,ap-1为整 数 ,矛盾即M不等于aN
同理可证N不等于aM
所以 M,N互质

然后就是解个方程了

#include
using namespace std;
int gcd(int x,int y)
{
     return x%y==0?y:gcd(y,x%y);
}
int main()
{
    int a,b;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        int c = gcd(a,b);
        b/=c;
        a/=c;
        int g = sqrt(a*a*1.0 - 4*b);
   //     printf("%d %d %d %d\n",a,b,g,c);
        if(g*g==a*a - 4*b)
        {
            int x1 =  a+g;
            if(x1%(2)==0)
            {
                int x2 = a-g;
                 if(x1>x2)
                    swap(x1,x2);
                if(x2%(2)==0)
                {
                    printf("%d %d\n",x1/2*c,x2/2*c);
                }
                else
                {
                    printf("No Solution\n");
                }
            }
            else
            {
                printf("No Solution\n");
            }
        }
        else
        {
            printf("No Solution\n");
        }
    }
}






(注:此网站文章大都来自公开的博客,如有原作者发现有侵权问题,请在此留言,我们会立刻删除相关文章。)

我的评价: