نظرية الأعداد

نظرية الأعداد هي مجرد اسم فاخر للعب بالأعداد الصحيحة (الأعداد الكاملة). لا كسور، لا أعداد عشرية - فقط أعداد نقية مثل 1، 5، 42، -10.

بحلول الآن، يجب أن تكون ملماً بالقسمة، أخذ الباقي عند القسمة، وتحديد الأنماط المتعلقة بهذه العمليات.

القاسم المشترك الأكبر (GCD)

القاسم المشترك الأكبر لعددين هو أكبر عدد يقسم كليهما دون ترك باقٍ.

على سبيل المثال:

GCD(12, 18) = 6 (كلاهما يمكن قسمته على 1، 2، 3، 6، ثم 6 هو الأكبر)
GCD(7, 13) = 1 (لا يشتركان في شيء سوى 1)

كيفية حسابه؟

من السهل نسبياً حساب GCD(a, b) إذا لم نهتم بالكفاءة. يمكن للمرء التكرار من 1 إلى \(max(a, b)\) والتحقق من أي عدد كان الأخير في قسمة كلا العددين \(a\) و \(b\)، دون باقٍ.

التعقيد الزمني لهذا الأسلوب هو \(\mathcal{O}(max(a, b))\).

كيفية حسابه بكفاءة؟ (خوارزمية إقليدس)

يمكننا القيام بما هو أفضل بكثير. لا تختبر كل عدد! هناك حيلة عمرها 2000 سنة: GCD(a, b) هو نفسه GCD(b, a % b). تستمر في أخذ الباقي حتى يصبح أحد الأعداد 0.

// Recursive way (The "standard" way)
int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

Tip

يمكنك أيضاً استخدام الدالة المدمجة لـ gcd. بالنسبة للإصدارات الأحدث (C++17 وما بعدها)، هناك دالة gcd(int, int). بالنسبة للإصدارات الأقدم من C++، يمكنك استخدام __gcd(int, int).

المضاعف المشترك الأصغر (LCM)

المضاعف المشترك الأصغر هو أصغر عدد يمكن لكلا العددين القسمة عليه.

فكر فيه على أنه “أول مرة تلتقي مضاعفاتهما”.

مضاعفات 4: 4، 8، 12، 16…
مضاعفات 6: 6، 12، 18…
LCM(4, 6) = 12

الصيغة

لا تحتاج إلى حلقة للعثور على هذا. استخدم GCD!

\[ \text{LCM}(a, b) = \frac{(a \times b)}{\text{GCD}(a, b)} \]

Caution

لتجنب الفيض (حصول العدد على قيمة كبيرة جداً)، اقسم أولاً: (a / gcd(a,b)) * b.

int lcm(int a, int b) {
    if (a == 0 || b == 0) return 0;
    return (a / gcd(a, b)) * b;
}

أمثلة على المسائل

Simplifying Fractions

معطى كسر، لنقل \(18/24\). تحتاج لإخراجه بأبسط صورة.

Solution

لتبسيط كسر، اقسم كلاً من الأعلى (البسط) والأسفل (المقام) على قاسمهما المشترك الأكبر.

#include <iostream>
#include <numeric> // for std::gcd
using namespace std;

int main() {
    int num = 18;
    int den = 24;
    
    int common = std::gcd(num, den);
    
    num /= common;
    den /= common;
    
    cout << num << "/" << den; // Outputs: 3/4
}

بإزالة أكبر عامل مشترك (6)، نحصل على النسخة الأبسط فوراً.

The Meeting Point

مصباحان يومضان بفترات زمنية مختلفة.

المصباح A يومض كل 12 ثانية.
المصباح B يومض كل 15 ثانية.

لقد ومضا معاً للتو. متى سيومضان معاً مرة أخرى؟

Solution

نبحث عن وقت \(T\) هو مضاعف لكل من 12 و 15. وتحديداً، أول (أصغر) وقت يحدث فيه ذلك. هذا بالضبط هو LCM.

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int a = 12;
    int b = 15;
    
    // LCM formula: (a * b) / GCD(a, b)
    int meet_time = std::lcm(a, b); 
    
    cout << "They meet again in " << meet_time << " seconds."; 
    // Output: 60 seconds
}