बड़े एन (फेसबुक हैकर कप) के लिए जोसेफस

Question

पिछले हफ्ते मैंने फेसबुक हैकर कप के दौर 1 बी में भाग लिया।

समस्याओं में से एक मूल रूप से Josephus problem

मैं जोसेफस समस्या से पहले अध्ययन किया एक असतत गणित की समस्या के रूप में था, इसलिए मैं मूल रूप से कैसे पुनरावृत्ति पाने के लिए समझ में:

f(n,k) = (f(n-1,k) + k) mod n, with f(1,k) = 0 

लेकिन वह didn फेसबुक हैकर कप में काम नहीं करते, क्योंकि एन का अधिकतम मूल्य 10^12 था। के के mak मूल्य 10^4 था।

विकिपीडिया एक दृष्टिकोण का उल्लेख करता है जब के छोटा होता है और एन बड़ा होता है। मूल रूप से लोगों को एक ही दौर से हटा दें, और फिर मरम्मत करें। लेकिन इसमें बहुत कुछ नहीं बताया गया है और मुझे समझ में नहीं आता कि मरम्मत क्यों काम करती है।

मैंने समाधान के लिए नमूना कार्य स्रोत कोड देखा, लेकिन मैं अभी भी अंतिम भाग को समझ नहीं पा रहा हूं।

long long joseph (long long n,long long k) { 
    if (n==1LL) return 0LL; 
    if (k==1LL) return n-1LL; 
    if (k>n) return (joseph(n-1LL,k)+k)%n; 
    long long cnt=n/k; 
    long long res=joseph(n-cnt,k); 
    res-=n%k; 
    if (res<0LL) res+=n; 
    else res+=res/(k-1LL); 
    return res; 
} 

हिस्सा मैं वास्तव में समझ में नहीं आता res-=n%k से शुरू कर रहा है (और लाइनों उसके बाद)। आप कैसे प्राप्त करते हैं कि परिणाम समायोजित करने का तरीका क्या है?

क्या कोई इस बात को पीछे छोड़ने के पीछे तर्क दिखा सकता है? या एक लिंक जो इसे प्राप्त करता है? (मुझे यूवीए या टॉपकोडर फ़ोरम पर कोई जानकारी नहीं मिली)

Answer 1

ठीक है, मुझे लगता है कि मैंने इसे क्रैक किया। पर कैसे पुनरावृत्तियों के साथ जाने के

आइए नज़र एन = 10 k = 3:

0 1 2 3 4 5 6 7 8 9 n=10,k=3 
1 2 3 4 5 6 0 n=7,k=3 

का निरीक्षण करें कैसे करने के लिए दूसरा यात्रा मानचित्र के तत्वों पहले एक: वे, n%k से स्थानांतरित कर रहे हैं, क्योंकि चक्र चहुंओर लपेटता। यही कारण है कि हम 10%3 घटाकर परिणाम को सही करते हैं। दूसरी पंक्ति में संख्या k-1 के समूहों में दिखाई देती है, इसलिए res/(k-1) द्वारा सुधार।

अन्य मामले पुनरावृत्तियों

0 1 2 3 4  n=5,k=3 
2 3 0 1  n=4,k=3 

अब j (4,3) रिटर्न 0, जो 5%3 द्वारा सही -2 होने का पता चला है के साथ आगे मारा जाता है। यह तब होता है जब दूसरी पंक्ति का परिणाम अंतिम समूह में होता है, जिसके परिणामस्वरूप n परिणामस्वरूप हमें हमारी मूल अनुक्रमणिका देगी।