如何在编程中求解线性Diophantine方程？ [英] How to solve Linear Diophantine equations in programming?

问题描述

我已经阅读了有关线性Diophantine方程的信息，例如 ax + by = c 被称为双显子方程，并且仅当 gcd（a ，b）除以c 。

I have read about Linear Diophantine equations such as ax+by=c are called diophantine equations and give an integer solution only if gcd(a,b) divides c.

这些等式在编程比赛中非常重要。当我遇到这个问题时，我只是在搜索互联网。我认为它是双色子方程的变体。

These equations are of great importance in programming contests. I was just searching the Internet, when I came across this problem. I think its a variation of diophantine equations.

问题：

我有两个人，人X和人你们俩都站在绳子中间。 X人可以向左或向右移动A或B单位。 Y人可以向左或向右移动C或D单位。现在，给我一个数字K，我必须找到它。绳索在[-K，K]范围内的可能位置，这样两个人都可以使用各自的电影多次到达该位置。 （给出了A，B，C，D和K）。

I have two persons,Person X and Person Y both are standing in the middle of a rope. Person X can jump either A or B units to the left or right in one move. Person Y can jump either C or D units to the left or right in one move. Now, I'm given a number K and I have to find the no. of possible positions on the rope in the range [-K,K] such that both the persons can reach that position using their respective movies any number of times. (A,B,C,D and K are given in question).

我的解决方案：

I认为该问题可以使用二阶方程来数学解决。

I think the problem can be solved mathematically using diophantine equations.

我可以为人X形成方程，例如 A x_1 + B y_1 = C_1，其中C_1属于[-K，K] ，对于人Y类似，例如 C x_2 + D y_2 = C_2，其中C_2属于[-K，K] 。

I can form an equation for Person X like A x_1 + B y_1 = C_1 where C_1 belongs to [-K,K] and similarly for Person Y like C x_2 + D y_2 = C_2 where C_2 belongs to [-K,K].

现在，我的搜索空间缩小为仅查找C_1和C_2相同的可能值的数量。这将是我对这个问题的答案。

Now my search space reduces to just finding the number of possible values for which C_1 and C_2 are same. This will be my answer for this problem.

要找到这些值，我只是找到 gcd（A，B）和 gcd（C，D），然后采用这两个 gcd 的 lcm 来获得 LCM（gcd（ A，B），gcd（C，D）），然后简单地计算[1，K]范围内的点数，该点数是此 lcm 的倍数。

To find those values I'm just finding gcd(A,B) and gcd(C,D) and then taking the lcm of these two gcd's to get LCM(gcd(A,B),gcd(C,D)) and then simply calculating the number of points in the range [1,K] which are multiples of this lcm.

我的最终答案是 2 * no_of_multiples in [1，K] + 1 。

我尝试在C ++代码中使用相同的技术，但是它不起作用（错误答案）。

I tried using the same technique in my C++ code, but it's not working(Wrong Answer).

这是我的代码：
http://pastebin.com/XURQzymA

我的问题是：谁能告诉我我是否正确使用了双色子方程？

My question is: can anyone please tell me if I'm using diophantine equations correctly ?

如果可以，谁能告诉我我的逻辑失败的可能情况。

If yes, can anyone tell me possible cases where my logic fails.

这些是一些测试

ABCDK以相同的顺序给出，相应的输出在下一行给出：

A B C D K are given as input in same sequence and the corresponding output is given on next line :

2 4 3 6 7

2 4 3 6 7

3

1 2 4 5 1

1 2 4 5 1

3

10 12 3 9 16

10 12 3 9 16

5

这是原始问题的链接。我已经用简单的语言写了原始问题。您可能会发现这很困难，但是如果您愿意，可以检查一下：

This is the link to original problem. I have written the original question in simple language. You might find it difficult, but if you want you can check it:

http://www.codechef.com/APRIL12/problems/DUMPLING/

请给我一些测试用例，以便

Please give me some test cases so that I can figure out where am I doing wrong ?

预先感谢。

推荐答案

ax + by = c 和 gcd （a，b）除以 c 。

1. 将a，b和c除以gcd（a，b）。


2. 现在gcd（a，b）== 1


3. 找到aU的解+ bV = 1，使用扩展的欧几里得算法


4. 乘积方程通过c。现在您有了a（Uc）+ b（Vc）= c


5. 您发现了解决方案 x = U * c 和 y = V * c

1. Divide a, b and c by gcd(a,b).
2. Now gcd(a,b) == 1
3. Find solution to aU + bV = 1 using Extended Euclidean algorithm
4. Multiply equation by c. Now you have a(Uc) + b (Vc) = c
5. You found solution x = U*c and y = V * c

这篇关于如何在编程中求解线性Diophantine方程？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！