a と b を足し合わせると c に到達できるかどうか、任意の 3 つの非負の数 a、b、c を見つけることを含む宿題を完了しようとしています。例：
a = 3、b = 5、c = 19 の場合、次の 1 番目のステップを実行します: (3,5) 2 番目のステップ: (3,8) 3 番目のステップ: (11,8) 4 番目のステップ: (19,8) したがってc に達しました。
これには、方程式 c = x a + y bのすべての正の解を見つけ、GCD(x,y) = 1 かどうかを確認することが含まれます。そうである場合、答えはイエスであり、そうでない場合、答えはノーです。
long long int cc = c; //saving the starting value of c
c=c-a; //a has to be in c at least once
while(c>0){ // we reduce c by a in each step until b divides c, which would mean we found
if(c%b==0){ //solutions to c=xa+yb or until c becomes <=0
y = (c/b); //evaluating y
x = ((cc - c)/a); //evaluating x
if(gcd(x,y)==1) //if it's correct, then it's possible, otherwise try other solutions
return true;
}
c=c-a; //reduce c by a
}
これは、最適化の助けが必要なコードの一部です。解を見つけるために、max(a,b) に設定した a によって c を繰り返し減らします。c からすべての 'a' を取り出すと、b で割り切れる数が得られ、したがって a が見つかりました。解決。その数を b で割り、その結果が解の y 部分です。その後、c から取り出したものを a で割り、解の x 部分を取得します。
正の解 x と y をより速く見つける方法はありますか? 拡張ユークリッド アルゴリズムについて聞いたことがありますが、それを実装する方法がわかりません。