J’ai lu sur les équations diophantiennes linéaires telles que ax+by=c sont appelées équations diophantiennes et ne donnent une solution entière que si gcd(a,b) divides c .

Ces équations sont d’une grande importance dans les concours de programmation. Je cherchais simplement sur Internet, quand je suis tombé sur ce problème. Je pense que c’est une variation des équations diophantiennes.

Problème:

J’ai deux personnes, la personne X et la personne Y, toutes deux debout au milieu d’une corde. La personne X peut sauter des unités A ou B à gauche ou à droite en un seul mouvement. La personne Y peut sauter les unités C ou D à gauche ou à droite en un seul mouvement. Maintenant, on me donne un numéro K et je dois trouver le non. de positions possibles sur la corde dans la plage [-K, K] de sorte que les deux personnes puissent atteindre cette position en utilisant leur film respectif autant de fois que nécessaire. (A, B, C, D et K sont donnés en question).

• Trouver un nombre premier?
• Comment utiliser un algorithme de recherche avec un vecteur de pointeurs sur des objects en c ++?
• Algorithme pour append la sum de chaque sous-tableau xor-sum possible
• Algorithme pour dessiner une forme d’onde à partir de l’audio
• Faut-il préférer les algorithmes STL aux boucles roulées à la main?

Ma solution:

Je pense que le problème peut être résolu mathématiquement en utilisant des équations diophantiennes.

Je peux former une équation pour la Personne X comme A x_1 + B y_1 = C_1 where C_1 belongs to [-K,K] et de même pour la Personne Y comme C x_2 + D y_2 = C_2 where C_2 belongs to [-K,K] .

Maintenant, mon espace de recherche se limite à trouver le nombre de valeurs possibles pour lesquelles C_1 et C_2 sont identiques. Ce sera ma réponse à ce problème.

Pour trouver ces valeurs, je cherche simplement gcd(A,B) et gcd(C,D) , puis je prends le cm de ces deux gcd pour obtenir LCM(gcd(A,B),gcd(C,D)) puis calculez simplement le nombre de points dans la plage [1, K] qui sont des multiples de ce lcm .

Ma réponse finale sera 2*no_of_multiples in [1,K] + 1 .

J’ai essayé d’utiliser la même technique dans mon code C ++, mais cela ne fonctionne pas (mauvaise réponse).

Ceci est mon code: http://pastebin.com/XURQzymA

Ma question est la suivante: quelqu’un peut-il me dire si j’utilise correctement les équations de diophantine?

Si oui, quelqu’un peut-il me dire des cas possibles où ma logique échoue.

Ce sont quelques-uns des cas de test qui ont été donnés sur le site avec l’énoncé du problème.

ABCDK est donné en entrée dans la même séquence et la sortie correspondante est donnée à la ligne suivante:

2 4 3 6 7

3

1 2 4 5 1

3

10 12 3 9 16

5

C’est le lien vers le problème original. J’ai écrit la question initiale dans un langage simple. Vous pourriez trouver cela difficile, mais si vous le souhaitez, vous pouvez le vérifier:

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

S’il vous plaît donnez-moi quelques cas de test afin que je puisse comprendre où je fais mal?

Merci d’avance.

• knuth hachage multiplicatif
• Tamis d’eratosthenes: peu optimisé
• comment implémenter un algorithme de sorting rapide en C ++
• Calcul de la moyenne mobile en C ++
• Fonctions de hachage STL

 unsigned long long l=g1/g; // cannot overflow unsigned long long res; if ((l * g2) / g2 != l) { // overflow case - l*g2 is very large, so k/(l*g2) is 0 res = 0; } else { l *= g2; res = k / l; }