2014
03-13

# 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;
}

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];
会报错 提示表达式必须含有常量值。该怎么修改呢。。