首页 > 代码库 > The Diophantine Equation hdu 3270

The Diophantine Equation hdu 3270

2024-07-16 23:38:25   218人阅读

每天一题萌萌哒

The Diophantine Equation

Time Limit: 1000/500 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1130    Accepted Submission(s): 290


Problem Description
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?
 

Input
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.
 

Output
You should output a single line containing either the word “Yes.” or “No.” for each input cases resulting either the equation is solvable in non-negative integers or not. An equation is solvable in non-negative integers if for non-negative integer value of x and y the equation is true. There should be a blank line after each test cases. Please have a look at the sample input-output for further clarification.
 

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

Sample Output
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.”
 

Author
Muhammed Hedayet


Source
HDOJ Monthly Contest – 2010.01.02 
题意：就是用扩展的欧几里得定理，如果有不懂得话就访问这个链接吧点击打开链接
既然知道姿势了就非常简单了可以把这个代码记下来，感觉一般求不定方程都一样：
#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 gcd(long x,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;
}

这个题除了用扩展的欧几里得还可以用直接暴搜，感觉是不是很暴力：
#include<cstdio>
#include<cstring>
#include<cstdlib>
char arr[30],temp[10];
int a,b,c;
int main()
{
    int i,j,len,x,y,cnt;
    while(scanf("%s",temp)!=EOF)
    {
        getchar();getchar();getchar();
        a=atoi(temp);
        if(a==0)
            a=1;
            scanf("%s",temp);
            getchar();getchar();getchar();
            b=atoi(temp);
            if(b==0)
                b=1;
            scanf("%d",&c);
            getchar();
            if(c>=0)
            {
                if(b==0&&c%a==0||a==0&&c%b==0)
                   {
                        printf("Yes.\n\n");
                        break;
                   }
                   for(x=0;(cnt=c-a*x)>=0;x++)
                   {
                       if(cnt%b==0)
                        {
                          printf("Yes.\n\n");
                            break;
                        }
                   }
                   if(cnt<0)
                     printf("No.\n\n");

            }
            else
                 printf("No.\n\n");
    }
    return 0;
}

稍稍的解释一下公式吧：ax+by=c ;
y=(c-ax)/b;记住分子要大于0，很简单吧。


联系
我们