指定された範囲内の最大公約数を見つけます

質問では、指定された範囲内で GCD を見つける必要があると述べています。 [p,q] の範囲内の 2 つの正の整数 x と y と 2 つの整数 p と q を取得します。 [p,q] の範囲にある数値 x と y の GCD (最大公約数) を見つける必要があります。数学では最大公約数として知られる GCD は、指定された 2 つの正の整数を除算する最大の正の整数です。指定された整数はゼロであってはなりません。任意の 2 つの正の整数 x および y は、gcd(x,y) と表されます。

たとえば、2 つの正の整数 6 と 9 があります。最大公約数 gcd(6,9) は、これら 2 つの数値を割る最大の数値であるため、3 になります。

しかし、この問題では、指定された範囲内で指定された 2 つの正の整数の最大公約数を見つける必要があります。例を通してこの問題を理解してみましょう。入力 x および y として 4 つの数値が与えられ、これらの数値の gcd を求めます。また、gcd の範囲を示す 2 つの数値、つまり [p,q] を求めます。

入力: x=8、y=12、p=1、q=3

出力: 2

説明 - 与えられた 2 つの数値 x と y の最大公約数は 4 であるため。しかし、4 は [1,3] の範囲内にありません。範囲 [1,3] の最大公約数は 2 で、これが目的の出力です。

入力: x=17、y=15、a=5、b=10

出力:-1

説明 - 数字 17 と 15 の最大公約数は 1 です。 1 が指定された範囲 [5,10] にないためです。指定された範囲に公約数がない場合は、出力として -1 を出力する必要があります。

＃＃＃アルゴリズム＃＃＃

問題を解決するために使用するアルゴリズムは非常に単純で、数学的に関連しています。まず、数値 x と y の gcd (最大公約数) を求めます。 C には、数値の最大公約数を出力として返す gcd() という組み込み関数があります。

＃＃＃文法＃＃＃ リーリー

ユークリッドのアルゴリズムの効率的な方法を使用して、2 つの数値の gcd を求めることもできます。両方が同時に動作し、時間計算量は O(log(min(x,y)).

になります。

さて、

単純な算術法則を使用して、2 つの数値の gcd で割った数値は 2 つの数値自体でも除算されると結論付けることができます

。したがって、for ループで i=1 から sqrt(gcd(x,y)) までを繰り返すと、数値の公約数をすべて取得できます。

次に、sqrt(gcd(x,y)) までの各 i が gcd(x,y) を除算するかどうかを確認します。 i で gcd(x,y) を割ると、gcd(x,y)/i は gcd の約数にもなり、したがって数値 x と y の公約数でもあると結論付けることができます。 例を通してこの概念を理解しましょう。 x と y がそれぞれ 32 と 48 であると仮定します。 gcd(18,27) は 16 です。したがって、この場合は、i=1 から i

Note

- 数値 n を任意の数値 x で割ると y が得られ、$\frac{n}{x}\:=\:y$ と表現できる場合、y は n を次の値で割ります。 x $ (x\:\times\:y\:=\:n)$。

このアルゴリズムは、この問題を解決する最も効果的な方法である可能性があります。このアルゴリズムに従いながら、共通分母が [a,b] の範囲内にあるかどうかを常にチェックします。そうでない場合は、max() 関数を使用して変数の約数を継続的に更新し、範囲内の最大公約数を取得します。

max() 関数の構文 リーリー aとbの最大値を返します。

＃＃＃方法＃＃＃

これが私たちが従うアプローチです -

指定された範囲内の最大公約数を計算する関数を初期化します。

指定された 2 つの正の数 x と y の gcd を計算します。
初期化変数名 ans = -1。
for ループで i=1 から i
If (gcd(x,y)%i)=0 は、i が [a,b] の範囲内にあるかどうかを確認し、max() 関数を使用してそれを ans に保存するかどうかを確認します。最大値を取得します。共通分母はこの範囲内にあります。
gcd/i が範囲内かどうかも確認し、範囲内であれば再度 max() 関数を使用して ans の値を更新します。
for ループ内のすべての反復が完了した後、ans を返します。

• ＃＃＃例＃＃＃
このメソッドの C での実装 -
• リーリー ＃＃＃出力＃＃＃ リーリー
  時間計算量: O(log(min(x,y)) sqrt(z))、
ここで、z は 2 つの数値 x と y の最大公約数です。

スペースの複雑さ: O(1)、

追加のスペースが使用されないため。

＃＃＃結論は＃＃＃

[a,b] の範囲内の 2 つの数値に対する gcd 問題を解く方法について説明しました。これは、さまざまな関数を使用して C で上記の問題を解決する方法です。

この記事が役に立ち、この問題に関連するすべての概念が明確になったことを願っています。

以上が指定された範囲内の最大公約数を見つけますの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。