首页 > ACM题库 > HDU-杭电 > HDU 3270-The Diophantine Equation-数论-[解题报告]HOJ
2014
03-13

HDU 3270-The Diophantine Equation-数论-[解题报告]HOJ

The Diophantine Equation

问题描述 :

We will consider a linear Diaphonic equation here and you are to find out whether the equation is solvable in non-negative integers or not.
Easy, is not it?

输入:

There will be multiple cases. Each case will consist of a single line expressing the Diophantine equation we want to solve. The equation will be in the form ax + by = c. Here a and b are two positive integers expressing the co-efficient of two variables x and y.
There are spaces between:
1. “ax” and ‘+’
2. ‘+’ and “by”
3. “by” and ‘=’
4. ‘=’ and “c”

c is another integer that express the result of ax + by. -1000000<c<1000000. All other integers are positive and less than 100000. Note that, if a=1 then ‘ax’ will be represented as ‘x’ and same for by.

输出:

There will be multiple cases. Each case will consist of a single line expressing the Diophantine equation we want to solve. The equation will be in the form ax + by = c. Here a and b are two positive integers expressing the co-efficient of two variables x and y.
There are spaces between:
1. “ax” and ‘+’
2. ‘+’ and “by”
3. “by” and ‘=’
4. ‘=’ and “c”

c is another integer that express the result of ax + by. -1000000<c<1000000. All other integers are positive and less than 100000. Note that, if a=1 then ‘ax’ will be represented as ‘x’ and same for by.

样例输入:

2x + 3y = 10
15x + 35y = 67
x + y = 0

样例输出:

Yes.

No.

Yes.

HINT: The first equation is true for x = 2, y = 2. So, we get, 2*2 + 3*2=10.
Therefore, the output should be “Yes.”

#include <stdio.h>
#include <string.h>

char str[100];

long long gcd(long long x,long long y)
{
    return y==0?x:gcd(y,x%y);
}

long long Ex_Euclid(long long a,long long b,long long &x,long long &y)
{
    long long ans,t;
    if (b==0)
    {
        x=1;
        y=0;
        ans=0;
        return ans;
    }
    ans=Ex_Euclid(b,a%b,x,y);
    t=x;
    x=y;
    y=t-(a/b)*y;
    return ans;
}

int main()
{
    int i,j,n;
    long long A,B,C,D,x,y,k,t;
    while(scanf("%s",str)!=EOF)
    {
        A=0;
        for (i=0;i<strlen(str)-1;i++)
        {
            A=A*10+str[i]-'0';
        }
        scanf("%s",str);
        scanf("%s",str);
        B=0;
        for (i=0;i<strlen(str)-1;i++)
        {
            B=B*10+str[i]-'0';
        }
        scanf("%s",str);
        scanf("%s",str);
        C=0;
        for (i=0;i<strlen(str);i++)
        {
            C=C*10+str[i]-'0';
        }
        if (A==0) A=1;
        if (B==0) B=1;
        D=gcd(A,B);
        if (C%D!=0)
        {
            printf("No.\n\n");
            continue;
        }
        n=Ex_Euclid(A,B,x,y);
        x=x*C/D;
        t=B/D;
        x=(x%t+t)%t;
        k=(C-A*x)/B;
        if (k>=0)
        {
            printf("Yes.\n\n");
            continue;
        }
        y=y*C/D;
        t=A/D;
        y=(y%t+t)%t;
        k=(C-B*y)/A;
        if (k>=0)
        {
            printf("Yes.\n\n");
            continue;
        }
        printf("No.\n\n");
    }
    return 0;
}

参考:http://blog.csdn.net/magicnumber/article/details/6612719


  1. 问题3是不是应该为1/4 .因为截取的三段,无论是否能组成三角形, x, y-x ,1-y,都应大于0,所以 x<y,基础应该是一个大三角形。小三角是大三角的 1/4.

  2. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. #include <stdio.h>
    int main(void)
    {
    int arr[] = {10,20,30,40,50,60};
    int *p=arr;
    printf("%d,%d,",*p++,*++p);
    printf("%d,%d,%d",*p,*p++,*++p);
    return 0;
    }

    为什么是 20,20,50,40,50. 我觉得的应该是 20,20,40,40,50 . 谁能解释下?

  5. 有一点问题。。后面动态规划的程序中
    int dp[n+1][W+1];
    会报错 提示表达式必须含有常量值。该怎么修改呢。。