美文网首页
I - A Simple Math Problem

I - A Simple Math Problem

作者: 陌路晨曦 | 来源:发表于2017-01-16 01:25 被阅读0次

    这是个数论题,题目给出两个正整数a,b;
    让我们寻找两个正整数X,Y,其满足X+Y=a,LCM(X,Y)=b;
    这个题可以用解方程做;
    因为XY=LCM(X,Y)GCD(X,Y);LCM(X,Y)=b;GCD(X,Y)=GCD(a,b);
    所以XY=b
    GCD(a,b);
    (z-x)(z-y)=zz-(x+y)z+xy;
    △t
    △t=(x+y)^2-4xy;
    z1=((x+y)+△t)/2 , z2=((x+y)-△t)/2 ;
    显然当△t<0方程无解,△t不是整数时,x,y也不是整数,所以这;两种时输出no solution;
    其他情况直接输出z1,z2;
    还有因为 integers a(1≤a≤2*104),b(1≤b≤109),所以变量 a,b,x,y,t 要用long long声明;

    #include<stdio.h>
    #include<math.h>
    int gcd(int a,int b)
    {
        return b==0? a:gcd(b,a%b);
    }
    int main()
    {
        long long  a,b,x,y,t;
        while(~scanf("%lld%lld",&a,&b))
        {
            b=gcd(a,b)*b;
            if(a*a-4*b<0)
            {
                printf("No Solution\n");
            }
            else
            {
                t=sqrt(a*a-4*b);
                x=(a+t)/2;
                y=x-t;
                if(t*t==a*a-4*b)
                {
                    printf("%lld %lld\n",y,x);
                    continue;
                }
                else
                {
                    printf("No Solution\n");
                }
            }   
        }
    }
    

    相关文章

      网友评论

          本文标题:I - A Simple Math Problem

          本文链接:https://www.haomeiwen.com/subject/jumubttx.html