ForHosting KIT · الرياضيات

نظرية لوكاس

احصل على C(n, k) بترديد عدد أولي دون مضروبات ضخمة: باقي C(1000, 200) على 7 هو 1، بكتابة العددين في الأساس 7 وضرب معاملات صغيرة لأرقامهما. تُعرض الأرقام لتتحقق من كل خطوة. مجانًا في متصفحك.

مجاني
يعمل في متصفحك
دون تسجيل
بياناتك لا تغادر جهازك

شغّل الأداة مجانًا اطّلع على الـAPI

استخدمها من الويبAPIالبريدTelegramالتطبيق قريبًا

مثال محلول

إذا أدخلت

N: 1,000
K: 200
القدرة (W): 7

تحصل على

النتيجة: 1
أرقام n: 6, 2, 6, 2
أرقام k: 4, 0, 4, 0

نظرية لوكاس هي الطريقة المعيارية لتقييم معامل ذات الحدين modulo عدد أولي عندما يكون n كبيرًا بما يكفي لجعل عاملي n غير عملي. الناتج هو بالضبط C(n, k) mod p؛ وإذا تجاوز أي رقم سفلي الرقم العلوي المقابل، تكون القيمة كلها صفرًا. تحتاج برمجة المسابقات ونظرية الأعداد التركيبية وواجبات التعمية إلى هذا الاختزال عندما تفيض العامليات المباشرة أو تكلف أكثر من اللازم.

ماذا تنص عليه نظرية لوكاس ومتى تحتاج إليها

في التركيبات الابتدائية يعدّ معامل ذات الحدين C(n, k) مجموعات k الجزئية من مجموعة ذات n عنصرًا ويساوي عاملي n مقسومًا على عاملي k مضروبًا في عاملي (n ناقص k). تصبح تلك الصيغة المغلقة عديمة الجدوى متى تجاوز n بضعة آلاف إذا احتجت فقط إلى الجواب modulo أولي صغير: تنفجر العامليات الوسيطة، وتفقد التقريبات العائمة الباقي الدقيق. تحلّ نظرية لوكاس، المسماة نسبةً إلى إدوارد لوكاس، هذه المسألة المعيارية تحديدًا.

يستخدم كل عامل وسائط أصغر من p، فيُحسب بحلقة ضربية قصيرة ومعكوسات معيارية توجد لأن p أولي وكل مقام أصغر من p. يجيب هذا الاختبار وحده عن أسئلة كثيرة من نوع «هل يقبل ذات الحدين القسمة على هذا الأولي؟» دون حساب جداء كامل.

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

كيف تطبق هذه الحاسبة نظرية لوكاس خطوة بخطوة

استدعِ القدرة بحقول صحيحة n وk وp. يجب أن يكون n وk عددين صحيحين غير سالبين على الأكثر تريليونًا؛ ويجب أن يكون p أوليًا بين اثنين ومليون وثلاثة شمولًا. تتحقق التنفيذ أولًا من الأنواع والحدود، ثم تشغّل اختبار أولية حتميًا بالقسمة التجريبية على p.

عند قبول p، يسير الحلّال أرقام الأساس p لـ n وk من الأقل أهمية إلى الأعلى. يستخدم كل ذات حدين صغير الصيغة الضربية مع معكوسات معيارية عبر مبرهنة فيرما الصغيرة (a مرفوعة إلى p ناقص اثنين modulo p)، منفَّذة بجداءات وسيطة دقيقة بـ BigInt حتى لا تُفقد الدقة ضمن الحدود المنشورة.

الحالات الحدّية مستقرة وموثّقة: عندما يكون k صفرًا أو يساوي n يكون الناتج واحدًا modulo p (أو صفرًا فقط إذا كان p واحدًا، وهذا مرفوض)؛ وعندما يتجاوز k قيمة n يكون الناتج صفرًا؛ وعندما يكون n وk كلاهما صفرًا تكون مصفوفات الأرقام الرقم الصفري الواحد والناتج واحدًا modulo p.

حالات الاستخدام

برمجة المسابقات وتمارين الأولمبياد

يمكن للمبرمجين التنافسيين التحقق من C(n, k) mod p لقيم n كبيرة مقابل حالات عيّنة ورؤية خطأ صريح عندما يكون المقاس مركبًا بالخطأ.

مختبرات نظرية الأعداد والتركيبات

يمكن للمدرّسين والطلاب فحص أرقام الأساس p إلى جانب الجداء المعياري أثناء تعلّم نظرية لوكاس واختبار الصفر لقابلية القسمة على أولي.

الأسئلة الشائعة

ماذا يحدث إذا لم يكن p أوليًا؟

تفيد الرسالة بأن p يجب أن يكون أوليًا (مثلًا عندما يكون p مركبًا أو يساوي 1). لا تُحتسب عملية التحقق الفاشلة.

أي خوارزمية تحسب ذات الحدين المعياري؟

تستخدم معاملات ذات الحدين الصغيرة للأرقام الصيغة الضربية مع معكوسات معيارية.

ما نطاقات n وk وp المقبولة؟

يجب أن يكون n وk عددين صحيحين غير سالبين على الأكثر 1,000,000,000,000. ويجب أن يكون p أوليًا من 2 إلى 1,000,003. تُرفض القيم خارج تلك الحدود أو p المركب.

كيف أعرف أن C(n, k) يقبل القسمة على عدد أولي؟

اكتب n وk في الأساس p وقارن بينهما رقمًا برقم. إذا كان أي رقم من k أكبر من الرقم المقابل له في n فالنتيجة 0، أي أن p يقسم معامل ذات الحدين.

ما باقي قسمة C(1000, 200) على 7؟

النتيجة 1. وتُعرض أيضًا الأرقام في الأساس 7 من الأدنى إلى الأعلى: 6، 2، 6، 2 للعدد 1000، و4، 0، 4، 0 للعدد 200. ولا يتجاوز أي رقم من 200 نظيره في 1000.

أدوات ذات صلة

للمطوّرين — الوصول عبر API

كل ما في هذه الصفحة متاح برمجيًا. هذا القسم موجّه للفرق التقنية التي تريد ربط الأداة بأنظمتها الخاصة؛ بقية المستخدمين يمكنهم استخدام الأداة أعلاه مباشرة دون الحاجة لقراءة ما يلي.

الـEndpoint

POSThttps://api.kit.forhosting.com/numth/lucas-theorem-binomial

صادِق على طلبك بترويسة Bearer، وأرسل طلب POST واحدًا لتدخل مهمتك قائمة التنفيذ فورًا؛ ثم تستلم النتيجة عبر webhook أو رابط موقّع.

استدعِ الخدمة من بيئتك

curl -X POST https://api.kit.forhosting.com/numth/lucas-theorem-binomial \
  -H "Authorization: Bearer $KIT_KEY" \
  -H "Content-Type: application/json" \
  -d '{"n":1000,"k":200,"p":7}'

const res = await fetch("https://api.kit.forhosting.com/numth/lucas-theorem-binomial", {
  method: "POST",
  headers: {
    "Authorization": `Bearer ${process.env.KIT_KEY}`,
    "Content-Type": "application/json"
  },
  body: JSON.stringify({
    "n": 1000,
    "k": 200,
    "p": 7
  })
});
const { task_id } = await res.json();

import os, requests

res = requests.post(
    "https://api.kit.forhosting.com/numth/lucas-theorem-binomial",
    headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
    json={
    "n": 1000,
    "k": 200,
    "p": 7
},
)
task_id = res.json()["task_id"]

<?php
$res = file_get_contents("https://api.kit.forhosting.com/numth/lucas-theorem-binomial", false, stream_context_create([
  "http" => [
    "method"  => "POST",
    "header"  => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
    "content" => '{"n":1000,"k":200,"p":7}',
  ],
]));
$task = json_decode($res, true);

body := bytes.NewBufferString(`{"n":1000,"k":200,"p":7}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/numth/lucas-theorem-binomial", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)

مثال على الطلب

{
  "n": 1000,
  "k": 200,
  "p": 7
}

مثال على الاستجابة

{
  "task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
  "type": "numth.lucas_theorem_binomial",
  "status": "queued",
  "_links": {
    "result": "/tasks/tsk_…/result"
  }
}

الواجهة غير متزامنة: تستلم task_id فور الإرسال، ويمكنك الاستعلام عن الحالة بمعدل طلب واحد في الثانية.

الأسعار

لكل طلب$0.002

السعر معلن كما تراه: لا tokens ولا نظام نقاط؛ وإن فشلت المهمة فلن تُحاسَب عليها.

الأخطاء

HTTP	الرمز	المعنى
`401`	`unauthorized`	مفتاح الوصول مفقود أو غير صالح؛ تحقق من ترويسة Bearer في طلبك.
`402`	`insufficient_balance`	رصيدك لا يكفي لتنفيذ هذه المهمة؛ أعد شحن الرصيد ثم أعد المحاولة.
`404`	`unknown_type`	نوع المهمة المطلوب غير موجود في الكتالوج — راجع الاسم المرسل في الطلب.
`429`	`rate_limited`	تجاوزت الحد المسموح من الطلبات؛ انتظر قليلًا ثم أعد المحاولة.

ملاحظات تقنية

بأعطاء أعداد صحيحة غير سالبة n وk وقاسم أولي p، توسّع النظرية n وk في الأساس p وتضرب معاملات ذات الحدين الصغيرة للأرقام C(n_i, k_i) modulo p. تقبل هذه الحاسبة n وk وp، وترفض المقاسات المركبة بخطأ invalid_input واضح، وتنفّذ مسار لوكاس حتميًا، وتعيد الناتج المعياري مع أرقام الأساس p حتى تتمكن من تدقيق كل خطوة دون إعادة اشتقاق التوسّع يدويًا.

ماذا تنص عليه نظرية لوكاس ومتى تحتاج إليها

اكتب n وk في الأساس p كمتتاليتي أرقام n_i وk_i، كل رقم أصغر بصرامة من p. عندئذ يكون C(n, k) متوافقًا modulo p مع جداء C(n_i, k_i) على i. نتيجة حاسمة هي اختبار الصفر: إذا كان الرقم السفلي k_i في أي موضع أكبر من n_i، فإن معامل ذات الحدين لذلك الرقم صفر وبالتالي C(n, k) يقبل القسمة على p.

كيف تطبق هذه الحاسبة نظرية لوكاس خطوة بخطوة

تفشل القيم المركبة والواحد والصفر والسوالب بـ invalid_input ورسالة تسمي p؛ ولا تُحسب تلك الإخفاقات. لكل زوج (n_i, k_i) إما يقطع إلى الصفر إذا تجاوز k_i قيمة n_i، أو يضرب الجداء الجاري في C(n_i, k_i) mod p. تعيد الاستجابة n وk وp وresult (الباقي من صفر إلى p ناقص واحد) وis_zero والمصفوفتين n_digits وk_digits بترتيب الرقم الأقل أهمية أولًا، وmethod مضبوطًا على السلسلة lucas.

الاستخدام العملي والحدود والتسعير والتسليم

استخدم أداة المتصفح عندما تريد فحصًا سريعًا بنظرية لوكاس أثناء قراءة ملاحظة في نظرية الأعداد، أو التحقق من عيّنة مسابقة، أو تصحيح روتين تركيب معياري. المدخلات المقبولة أعداد صحيحة غير سالبة n وk حتى تريليون وأوليّات p من اثنين إلى مليون وثلاثة. إذا احتجت C(n, k) الصحيح بلا قيد، أو صف ذات حدين لكل k، أو معاملات معيارية لمقاسات مركبة عبر مبرهنة الباقي الصينية، فاستخدم قدرة مخصصة؛ تتوقف هذه الأداة عمدًا عند لوكاس لأولي p مُتحقَّق منه حتى يبقى العقد بسيطًا وقابلًا للتدقيق. استخدم API عندما يحتاج مصحّح أو منصة تعليم أو سكربت إلى تقييمات كثيرة لـ C(n, k) mod p دون تضمين بوابة أولية ومسار أرقام. كل طلب ناجح عنصر فوترة واحد بسعر $0.002؛ ولا تستهلك إخفاقات التحقق والمقاسات غير الأولية الرصيد. النتائج حتمية: يعطي الثلاثي نفسه دائمًا الباقي نفسه ومصفوفات الأرقام نفسها وعلامة is_zero نفسها. اربط نقطة النهاية بمساعدات الأولمبياد، وصناديق رمل البرمجة التنافسية، وعروض تعليم التعمية التي تمس معاملات ذات الحدين modulo أوليّات صغيرة، أو أي خط أنابيب لأعداد صحيحة يفضّل الحساب المعياري الدقيق على المكتبات التقريبية. لأن الوحدة عنصر واحد والمحرك parse خالص، تبقى الكمون منخفضة ويعكس القناة الويب المجاني API المدفوع دون مسار شيفرة ثانٍ قد ينحرف.

حالات التكامل

مصحّحات الواجبات وخطوط الأنابيب المعيارية

يمكن للمصحّحات الآلية والسكربتات تأكيد البواقي، واكتشاف p غير الأولي عبر invalid_input، والإبقاء على كل جداء وسيط ضمن الحدود الموثّقة.

أسئلة تقنية

كيف أحسب C(n,k) mod p بهذه الـ API؟

أرسل JSON بحقول صحيحة n وk وp (p أولي) إلى numth.lucas_theorem_binomial. عند النجاح تعيد الاستجابة result في 0..p−1 وis_zero ومصفوفات أرقام الأساس p وmethod "lucas".

هل حاسبة نظرية لوكاس لذات الحدين مجانية؟

تعمل أداة المتصفح مجانًا على جهازك. تستخدم استدعاءات API رصيد KIT المدفوع مسبقًا بسعر $0.002 لكل عنصر ناجح؛ ولا تُحتسب المدخلات غير الصالحة والمقاسات غير الأولية.

اطّلع على توثيق KIT الكامل ←

شغّل الأداة مجانًا

مثال محلول

ماذا تنص عليه نظرية لوكاس ومتى تحتاج إليها

كيف تطبق هذه الحاسبة نظرية لوكاس خطوة بخطوة

حالات الاستخدام

برمجة المسابقات وتمارين الأولمبياد

مختبرات نظرية الأعداد والتركيبات

الأسئلة الشائعة

أدوات ذات صلة

للمطوّرين — الوصول عبر API

الـEndpoint

استدعِ الخدمة من بيئتك

مثال على الطلب

مثال على الاستجابة

الأسعار

الأخطاء

ملاحظات تقنية

ماذا تنص عليه نظرية لوكاس ومتى تحتاج إليها

كيف تطبق هذه الحاسبة نظرية لوكاس خطوة بخطوة

الاستخدام العملي والحدود والتسعير والتسليم

حالات التكامل

مصحّحات الواجبات وخطوط الأنابيب المعيارية

أسئلة تقنية

شكرًا