द्वारा या तो एक्स 1 और एन विभाज्य के बीच सभी संख्याओं का योग ढूँढें या y

Question

कहते हैं कि हम 3 संख्या N, x और y जो हमेशा से रहे हैं >=1 है।

एन x और y और x से अधिक y से अधिक होगा।

अब हमें की आवश्यकता है जो 1 और एन के बीच सभी संख्याओं का योग पाएं जो x या y द्वारा विभाजित हैं।

मैं इस के साथ आया था:

sum = 0; 
for(i=1;i<=N;i++) 
{ 
    if(i%x || i%y) 
    sum += i; 
} 

वहाँ एक रास्ता पाश के लिए टाल राशि पाने की बेहतर तरीका है?

मैं कई दिनों से अपने सिर को तेज़ कर रहा हूं लेकिन कुछ भी बेहतर नहीं मिला है।

यदि N का मान ऊपरी सीमा है तो हम प्रक्रिया को तेज़ करने के लिए एक लुकअप विधि का उपयोग कर सकते हैं।

सभी को धन्यवाद।

मैं एक सी/सी ++ आधारित समाधान चाहता था। क्या ऐसा करने के लिए एक अंतर्निहित कार्य है? या मुझे एल्गोरिदम कोड करना है?

Answer 1

हां। आप लूप को पूरी तरह से रद्द कर सकते हैं और निरंतर समय में योग पा सकते हैं।

x के गुणकों और y के गुणकों संक्षेप और आम एकाधिक (रों) कि जोड़ा गया दो बार हमें आवश्यक राशि देना चाहिए घटाकर Inclusion–exclusion principle के अनुसार।

Required Sum = sum of (multiples of x that are <= N) +  
       sum of (multiples of y that are <= N) - 
       sum of (multiples of (x*y) that are <= N) 

उदाहरण:

N = 15 
x = 3 
y = 4 

Required sum = (3 + 6 + 9 + 12 + 15) + // multiples of 3 
       (4 + 8 + 12) -   // multiples of 4 
       (12)     // multiples of 12 

देखा जैसा कि ऊपर हम 12 घटाना के रूप में यह दो बार जोड़ा गया है क्योंकि यह एक आम गुणक है था।

संपूर्ण एल्गोरिदम ओ (1) कैसा है?

Let x के गुणकों का योग sum(x, N) जो N से कम या उसके बराबर हैं।

sum(x,N) = x + 2x + ... + floor(N/x) * x 
     = x * (1 + 2 + ... + floor(N/x)) 
     = x * (1 + 2 + ... + k) // Where k = floor(N/x) 
     = x * k * (k+1)/2   // Sum of first k natural num = k*(k+1)/2 

अब k = floor(N/x) को निरंतर समय में गणना की जा सकती है।

एक बार k ज्ञात sum(x,N) को निरंतर समय में गणना की जा सकती है।

तो आवश्यक राशि भी निरंतर समय में गणना की जा सकती है।

संपादित करें:

उपरोक्त चर्चा सच है केवल जब x और yco-primes हैं।यदि नहीं, तो x*y के स्थान पर हमें LCM(x,y) का उपयोग करने की आवश्यकता है। एलसीएम को खोजने के कई तरीके हैं जिनमें से एक जीसीडी द्वारा उत्पाद को विभाजित करना है। अब जीसीडी को निरंतर समय में गणना नहीं की जा सकती है लेकिन इसकी time complexity रैखिक समय से काफी कम हो सकती है।

Answer 2

एक नंबर एक्स से विभाज्य है, तो यह एक्स की एक बहु हो गया है। यदि कोई संख्या वाई द्वारा विभाजित है, तो इसे वाई का एक बहु होना चाहिए।

मेरा मानना ​​है कि, यदि आप x और y के सभी गुणकों के लिए पाश के लिए एक करते हैं, और सभी डुप्लिकेट से बचने, आप एक ही जवाब मिलना चाहिए।

मेरे सिर से बाहर

, प्रकार के बारे में कुछ:

sum = 0 
for(i=x; i<=n; i+=x) 
    sum += i; 

for(i=y; i<=n; i+=y) 
    if(y % x != 0) 
     sum += i;