أكبر GCD بين بعض الأرقام

Question

لدينا بعض الأرقام غير السالبة.نريد العثور على الزوج ذو الحد الأقصى لـ gcd.في الواقع هذا الحد الأقصى هو أكثر أهمية من الزوج!على سبيل المثال إذا كان لدينا:

2 4 5 15

جي سي دي(2,4)=2

جي سي دي(2,5)=1

جي سي دي(2,15)=1

جي سي دي(4,5)=1

جي سي دي(4,15)=1

جي سي دي(5,15)=5

الجواب هو 5.

Answer 1

هناك حل سيستغرق o (n):

دع أرقامنا تكون a_i. أولا ، حساب m=a_0*a_1*a_2*.... لكل رقم A_I ، احسب gcd(m/a_i, a_i). الرقم الذي تبحث عنه هو الحد الأقصى لهذه القيم.

لم أثبت أن هذا صحيح دائمًا ، لكن في مثالك ، يعمل:

m=2*4*5*15=600,

max(gcd(m/2,2), gcd(m/4,4), gcd(m/5,5), gcd(m/15,15))=max(2, 2, 5, 5)=5

---

ملاحظة: هذا غير صحيح. إذا كان الرقم a_i له عامل p_j يتكرر مرتين ، وإذا كان رقمين آخران يحتويان أيضًا على هذا العامل ، p_j, ، ثم تحصل على النتيجة غير الصحيحة p_j^2 بدلا من p_j. على سبيل المثال ، للمجموعة 3, 5, 15, 25, ، لقد حصلت 25 كما الجواب بدلا من 5.

ومع ذلك ، لا يزال بإمكانك استخدام هذا لتصفية الأرقام بسرعة. على سبيل المثال ، في الحالة أعلاه ، بمجرد تحديد 25 ، يمكنك أولاً إجراء البحث الشامل a_3=25 مع gcd(a_3, a_i) للعثور على الحد الأقصى الحقيقي ، 5, ، ثم تصفية gcd(m/a_i, a_i), i!=3 التي أقل من أو تساوي 5 (في المثال أعلاه ، يقوم هذا بتصفية جميع الآخرين).

---

تمت إضافة للتوضيح والتبرير:

لمعرفة لماذا يجب أن ينجح هذا ، لاحظ ذلك gcd(a_i, a_j) يقسم gcd(m/a_i, a_i) للجميع j!=i.

لنتصل gcd(m/a_i, a_i) كما g_i, ، و max(gcd(a_i, a_j),j=1..n, j!=i) كما r_i. ما أقوله أعلاه هو g_i=x_i*r_i, ، و x_i هو عدد صحيح. من الواضح أن r_i <= g_i, ، في ذلك n عمليات GCD ، نحصل على حد أعلى r_i للجميع i.

الادعاء أعلاه ليس واضحا جدا. دعنا نفحص الأمر أكثر عمقًا لنرى لماذا صحيح: GCD من a_i و a_j هو نتاج جميع العوامل الأولية التي تظهر في كليهما a_i و a_j (حسب التعريف). الآن ، اضرب a_j برقم آخر ، b. GCD من a_i و b*a_j إما يساوي gcd(a_i, a_j), ، أو مضاعف منه ، لأن b*a_j يحتوي على جميع العوامل الرئيسية a_j, ، وبعض العوامل الأولية التي ساهمت بها b, ، والتي يمكن أيضًا إدراجها في عامل a_i. في الواقع، gcd(a_i, b*a_j)=gcd(a_i/gcd(a_i, a_j), b)*gcd(a_i, a_j), ، أظن. لكن لا يمكنني رؤية طريقة للاستفادة من هذا. قون

على أي حال ، في بنائنا ، m/a_i هو ببساطة اختصار لحساب المنتج للجميع a_j, ، أين j=1..1, j!=i. نتيجة ل، gcd(m/a_i, a_i) يحتوي على كل gcd(a_i, a_j) كعامل. لذلك ، من الواضح أن الحد الأقصى لنتائج GCD الفردية هذه سوف تقسم g_i.

الآن ، الأكبر g_i من الأهمية بمكان بالنسبة لنا: إنه إما الحد الأقصى لـ GCD نفسه (إذا x_i هو 1) ، أو مرشح جيد لكونه واحد. للقيام بذلك ، نفعل آخر n-1 عمليات GCD ، وحساب r_i صراحة. ثم ، نحن نسقط كل شيء g_j اقل او يساوي r_i كمرشحين. إذا لم يكن لدينا أي مرشح آخر ، فقد انتهينا. إذا لم يكن الأمر كذلك ، فإننا نلتقط الأكبر التالي g_k, وحساب r_k. إذا r_k <= r_i, ، نسقط g_k, وكرر مع آخر g_k'. إذا r_k > r_i, ، نرشح المتبقية g_j <= r_k, ، ثم كرر.

أعتقد أنه من الممكن إنشاء مجموعة أرقام تجعل هذه الخوارزمية تعمل في O (n^2) (إذا فشلنا في تصفية أي شيء) ، ولكن في مجموعات الأرقام العشوائية ، أعتقد أنها ستتخلص بسرعة من القطع الكبيرة من مرشحين.

Answer 2

يمكنك استخدام خوارزمية الإقليدية للعثور على GCD من رقمين.

while (b != 0) 
{
    int m = a % b;
    a = b;
    b = m;
}
return a;

Answer 3

إذا كنت تريد بديلاً للخوارزمية الواضحة، فافترض أن أرقامك موجودة في نطاق محدد، ولديك الكثير من الذاكرة، فيمكنك التغلب على وقت O(N^2)، حيث N هو عدد القيم:

• قم بإنشاء مصفوفة من نوع عدد صحيح صغير، وفهرسة 1 إلى الحد الأقصى للإدخال.يا(1)
• لكل قيمة، قم بزيادة عدد كل عنصر في الفهرس الذي يعد عاملاً للرقم (تأكد من عدم الالتفاف).على).
• بدءًا من نهاية المصفوفة، قم بالمسح مرة أخرى حتى تجد القيمة >= 2.يا(1)

يخبرك هذا بالحد الأقصى لـ GCD، لكنه لا يخبرك بالزوج الذي أنتجه.بالنسبة لإدخال المثال الخاص بك، تبدو المصفوفة المحسوبة كما يلي:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
4 2 1 1 2 0 0 0 0 0  0  0  0  0  1

لا أعرف ما إذا كان هذا أسرع بالفعل بالنسبة للمدخلات التي يتعين عليك التعامل معها.العوامل الثابتة المعنية كبيرة:الحد الأقصى لقيمك والوقت اللازم لتحليل قيمة ضمن هذا الحد.

لا يتعين عليك تحليل كل قيمة إلى عوامل - يمكنك استخدام الحفظ و/أو قائمة الأعداد الأولية التي تم إنشاؤها مسبقًا.مما يعطيني فكرة أنك إذا كنت تقوم بحفظ التحليل، فلن تحتاج إلى المصفوفة:

• قم بإنشاء مجموعة فارغة من int، والقيمة الأفضل حتى الآن 1.
• لكل عدد صحيح الإدخال:
  • إذا كان أقل من أو يساوي الأفضل حتى الآن، تابع.
  • تحقق مما إذا كان في المجموعة.إذا كان الأمر كذلك، الأفضل حتى الآن = الحد الأقصى (الأفضل حتى الآن، هذه القيمة)، تابع.ان لم:
    • إضافته إلى المجموعة
    • كرر لجميع عوامله (أكبر من الأفضل حتى الآن).

يمكن أن تكون عملية الإضافة/البحث في مجموعة ما هي O(log N)، على الرغم من أن ذلك يعتمد على بنية البيانات التي تستخدمها.تحتوي كل قيمة على عوامل O(f(k)) حيث k هي القيمة القصوى ولا أستطيع تذكر ما هي الدالة f...

السبب وراء انتهائك من القيمة بمجرد مواجهتها في المجموعة هو أنك عثرت على رقم يمثل عاملاً مشتركًا بين قيمتين مدخلتين.إذا واصلت التحليل، فستجد فقط أرقامًا أصغر، وهو أمر غير مثير للاهتمام.

لست متأكدًا تمامًا من أفضل طريقة لتكرار العوامل الأكبر.أعتقد أنه من الناحية العملية قد يتعين عليك تحقيق التوازن:أنت لا تريد أن تفعلها بترتيب تنازلي تمامًا لأنه من الصعب إنشاء عوامل مرتبة، ولكنك أيضًا لا تريد العثور على جميع العوامل فعليًا.

حتى في عوالم O(N^2)، قد تتمكن من التغلب على استخدام الخوارزمية الإقليدية:

قم بتحليل كل رقم بالكامل، وتخزينه كسلسلة من الأسس الأولية (على سبيل المثال 2 هو {1}، 4 هو {2}، 5 هو {0، 0، 1}، 15 هو {0، 1، 1}) .ثم يمكنك حساب gcd(a,b) عن طريق أخذ القيمة الدنيا في كل فهرس وضربها مرة أخرى.لا توجد فكرة عما إذا كان هذا أسرع من إقليدس في المتوسط، ولكن قد يكون كذلك.ومن الواضح أنه يستخدم تحميل المزيد من الذاكرة.

Answer 4

التحسينات التي يمكنني التفكير فيها

1) ابدأ بأكبر العدسين حيث من المحتمل أن يكون لهما معظم العوامل الأولية ، وبالتالي من المحتمل أن يكون لديهم العوامل الأولية الأكثر مشتركة (وبالتالي أعلى GCD).

2) عند حساب GCDs للأزواج الأخرى ، يمكنك إيقاف حلقة خوارزمية الإقليدية إذا حصلت على أقل من أعظم GCD الحالي.

خارج الجزء العلوي من رأسي ، لا يمكنني التفكير في طريقة يمكنك من خلالها تحديد أعظم GCD لزوج ما دون محاولة حل كل زوج على حدة (وتحسين ما هو مذكور أعلاه).

إخلاء المسئولية: لم أنظر أبدًا إلى هذه المشكلة من قبل وما سبق هو خارج رأسي. قد تكون هناك طرق أفضل وقد أكون مخطئًا. يسعدني مناقشة أفكاري بمزيد من الطول إذا أراد أي شخص. قون

Answer 5

لا يوجد O(n log n) حل لهذه المشكلة بشكل عام. في الواقع ، أسوأ حالة O(n^2) في عدد العناصر في القائمة. النظر في المجموعة التالية من الأرقام:

2^20 3^13 5^9 7^2*11^4 7^4*11^3

فقط GCD في آخر اثنين هو أكبر من 1 ، ولكن الطريقة الوحيدة لمعرفة أنه من النظر إلى GCDs هي تجربة كل زوج ولاحظ أن أحدهما أكبر من 1.

لذا ، فأنت عالق مع نهج Try-Clor-Pair الممل في كل مكان ، ربما مع بعض التحسينات الذكية لتجنب القيام بعمل لا داعي له عندما تجد بالفعل GCD كبير (مع التأكد من أنك لا تفوت أي شيء ).

Answer 6

مع بعض القيود ، على سبيل المثال ، توجد الأرقام الموجودة في المصفوفة ضمن نطاق معين ، على سبيل المثال 1-1E7 ، يمكن التنفيذ في O (nlogn) / o (Max * logmax) ، حيث أقصى القيمة الممكنة في A.

مستوحاة من خوارزمية الغربال ، وصادفها في أ تحدي hackerrank - هناك يتم ذلك لمصفوفتين. تحقق من الافتتاحية.

• ابحث عن دقيقة (أ) وحد أقصى (أ) - س (ن)
  قم بإنشاء قناع ثنائي ، لتمييز أي عناصر تظهر في النطاق المحدد ، من أجل البحث O (1) ؛ س (ن) لبناء ؛ o (max_range) التخزين.
• لكل رقم A في النطاق (دقيقة (أ) ، كحد أقصى (أ)):
  لـ AA = A ؛ aa <max (a) ؛ aa += a:
  • إذا كانت AA في A ، زيادة عداد لـ AA ، وقارنها بـ MAX_GCD الحالي ، إذا كان العداد> = 2 (أي ، لديك رقمين قابلان للقسمة بواسطة AA) ؛
  • تخزين أفضل مرشحين لكل مرشح GCD.
  • يمكن أن تتجاهل أيضًا العناصر التي تكون أقل من MAX_GCD الحالي ؛

الإجابة السابقة: لا يزال O (n^2) - فرز الصفيف ؛ يجب القضاء على بعض المقارنات غير الضرورية ؛

max_gcd = 1
# assuming you want pairs of distinct elements.
sort(a) # assume in place
for ii = n - 1: -1 : 0 do
    if a[ii] <= max_gcd
        break
    for jj = ii - 1 : -1 :0 do
        if a[jj] <= max_gcd 
            break
        current_gcd = GCD(a[ii], a[jj])
        if current_gcd > max_gcd:
            max_gcd = current_gcd

هذا يجب أن ينقذ بعض الحساب غير الضروري.

Answer 7

كود مزيف

function getGcdMax(array[])

    arrayUB=upperbound(array)
    if (arrayUB<1)
        error
    pointerA=0
    pointerB=1

    gcdMax=0

    do
        gcdMax=MAX(gcdMax,gcd(array[pointera],array[pointerb]))
        pointerB++
        if (pointerB>arrayUB)
            pointerA++
            pointerB=pointerA+1
    until (pointerB>arrayUB)

    return gcdMax