O（n^2）時間の複雑さよりも良い点で、行ax + by = cにある整数のすべての順序付きペアを見つける

Question

3つのlong int変数a、b、cを入力できるコードを記述しようとしています。 コードはax + by = cとなるようにすべての整数（x、y）を見つけるべきですが、入力値は2 * 10^9までです。私はこれを効率的に行う方法がわかりません。私のアルゴリズムはO（n^2）です。このような大きな入力に対しては本当に悪いです。どうすればいいですか？ここに私のコード - だ

typedef long int lint; 

struct point 
{ 
lint x, y; 
}; 

int main() 
{ 
lint a, b, c; 
vector <point> points; 
cin >> c >> a >> b; 
for(lint x = 0; x < c; x++) 
    for(lint y = 0; y < c; y++) 
    { 
     point candidate; 
     if(a*x + b*y == c) 
     { 
      candidate.x = x; 
      candidate.y = y; 
      points.push_back(candidate); 
      break; 
     } 
    } 
} 

Answer 1

あなたがxの任意の値のためにyを解くために、本当に些細な数学のほんの少しを適用することができますように思えます。 ax + by = c最低料金：非ゼロb を想定し

ax + by = c 

by = c - ax 

、我々はその後、取得：手でそれと

y = (c - ax)/b 

を、我々はに差し込み、ループ内でxの私たちの価値観を生成することができます上記の方程式を計算し、照合値yを計算し、それが整数かどうかを確認してください。もしそうなら、その（x、y）ペアを加えて、次の値のxに進みます。

あなたは、当然のことながら、次のステップを行い、さらには、我々はO（N ）から移動してきたことをやってなくてxの値が整数、しかしている必要yにつながることになる見つけ出すことができO（N）は、はるかに合理的な時間枠でタスクを完了するのに十分な可能性が高いです。もちろん

---

1. 、bが0であれば、その後、by項はゼロであるので、我々は、我々はその後、x = c/aになることができax = cを持っているので、私達はそれからちょうどxが整数であることを確認する必要がありますもしそうならば、の候補の値がyのすべてのペアは、正しいcを生成します。