गणना (ए^बी)% एमओडी

मैं पाउ (ए, बी)% एमओडी के मूल्य की गणना के लिए कोड करना चाहता हूं। मैं कोड में सी ++ का उपयोग करता हूं।गणना (ए^बी)% एमओडी

लेकिन समस्या यह है कि बी का मूल्य बहुत बड़ा हो सकता है। मुझे लॉग (बी) समय जटिलता विधि पता है। लेकिन, बी का मान डेटा प्रकार में फिट नहीं हो सकता है जो सी ++ के "लंबे समय तक" है। उदाहरण के लिए बी 1000000000 वें फाइबोनैकी संख्या हो सकती है। इतनी बड़ी संख्या की सटीक गणना स्वयं ही संभव नहीं है (समय सीमा में)।

पीएस :

पाउ (ए, बी) का मतलब है * ए * ए * ए * ... बी टाइम्स।
एक्स% एमओडी का मतलब एमओडी द्वारा एक्स को विभाजित करने पर प्राप्त शेष है।

स्रोत

2012-06-30 Gurpreet Singh

संभवतः डुप्लिकेट [सी ++ में मनमाना लंबाई पूर्णांक को संभालें] (http://stackoverflow.com/questions/8146938/handle-arbitrary-length-integers-in-c) –

केवल स्पष्टीकरण के लिए, सी ++ '^' में है एक्सओआर ओपेराटो आर, एक एक्सपोनेंट ऑपरेटर नहीं (आप कुछ सुंदर परिणामों के साथ खत्म हो जाएंगे, पहले हाथ अनुभव)। मेरा मानना है कि आपको 'Math.exp (a, b) ' – nbrooks

@nbrooks का उपयोग करना होगा: जबकि आप निश्चित रूप से सही हैं कि C++ XOR का अर्थ'^'का उपयोग करता है,' Math.exp (a, b) 'नहीं दिखता है जैसे सी ++ (और नाम के आधार पर, मैं उम्मीद करता हूं कि यह घातीय गणना करे, एक शक्ति को संख्या न बढ़ाएं)। –

यह एक सामान्य कार्य है। कृपया (या, वास्तव में, कृपया!) Euler's totient function के बारे में पढ़ें।

और फिर Euler's theorem।

बात यह है कि आप नाटकीय रूप से^बी से^^ (बी% फाई (एमओडी) को कम कर सकते हैं। हां, आपको किसी प्रकार की पूर्णांक कारक बनाने की विधि की आवश्यकता होगी, लेकिन फिर भी, वास्तव में आवश्यक शक्ति की गणना करने के बारे में कोई पागल विचार नहीं है।

हमने अपने युवाओं में हाथ से ऐसे नमूने किए हैं :) यहां तक कि जब 32/64 बिट सीमा से कहीं अधिक संख्याएं हैं।

संपादित करें: ठीक है, आप रहते हैं और सीखते हैं। 2008 में परिणाम प्राप्त किया जाता है:

"totient असतत फूरियर gcd का बदलना है: (Schramm (2008))"

तो गणना करने के लिए फ़ाई (ख) एक अपने कारकों पता करने की जरूरत नहीं है।

संपादित करें (2):

और Carmichael's function क्या आप किसी भी ए, बी और एमओडी के लिए सही जवाब पाने के लिए गणना करने के लिए की जरूरत है।

स्रोत

2012-06-30 08:15:45

धन्यवाद विक्टर। मुझे वांछित मिला। मदद के लिए धन्यवाद ... :-) बीटीडब्ल्यू, मुझे कुल कार्य के बारे में पता था, लेकिन उस यूलर के प्रमेय के बारे में नहीं ... –

"तो फाई (बी) की गणना करने के लिए किसी को इसके कारकों को जानने की आवश्यकता नहीं है।" यह शायद 'phi (बी)' की गणना के लिए एक व्यावहारिक विधि की तरह दिखता है, हालांकि। –

@ मार्क डिकिंसन: हां, यही कारण है कि मैंने श्राम के पेपर के बारे में टिप्पणी को जोड़ा। इसमें केवल एक ही अलग फूरियर ट्रांसफॉर्म शामिल है। –

पहले: ^ सी में/C++ नहीं शक्तियों के लिए ऑपरेटर है। वास्तव में, इसके लिए कोई ऑपरेटर नहीं है। ^ थोड़ा सा एक्सओआर का प्रतिनिधित्व करता है। आपको pow(base, exp) का उपयोग करना होगा जो शीर्षलेख math.h या cmath में पाया जा सकता है।

इस तरह के बड़ी संख्या के लिए, double या long double का उपयोग कर (सटीक लंबाई और और डेटाटाइप्स अपने मंच के आधार पर भिन्न हो सकता है जिसके परिणामस्वरूप), लेकिन कुछ समय में आप सटीक मुद्दों पर ठोकर करेंगे, इसलिए आपके उपयोग के मामले पर निर्भर करता है, मूल्यों का आकार आपकी सबसे अच्छी शर्त कस्टम डेटाटाइप का उपयोग कर सकती है (संपादित करें: उदाहरण के लिए किसी एक लिंक किए गए प्रश्नों में पाए गए पुस्तकालयों में से एक)।

स्रोत

2012-06-30 07:56:22 Mario

यह वास्तव में एक संख्या-सैद्धांतिक प्रश्न है। यहां बलपूर्वक बल देने की आवश्यकता नहीं है।कार्य का पूरा बिंदु कुछ साधारण क्लासिक प्रमेय की श्रेष्ठता को प्रदर्शित करना है। मेरा जवाब देखें –

दिलचस्प, अनुमान है कि आपने बस मेरे सप्ताहांत के खाली समय चुरा लिया है, उस पर पढ़ने के लिए जा रहा है। :) – Mario

यह पुस्तक अच्छी है: http://books.google.ru/books/about/Number_Theory.html?id=njgVUjjO-EAC इसके अलावा इवान विनोद्रेडोव की किताबें अच्छी हैं। जीन-पियरे सेरे का "कोर्स डी अंकगणित" और भी संभावनाएं खुलता है। –

मैं एक विशेष गणित पुस्तकालय का उपयोग करने का सुझाव देता हूं। यह भी क्रिप्टो की तरह दिखता है, इसलिए मैं एक क्रिप्टो लाइब्रेरी का उपयोग करने का सुझाव देता हूं। जीएनयू एक ऐसा है जिसके लिए आप उपयोग कर सकते हैं। ऐसा इसलिए है क्योंकि कई मामलों में क्रिप्टो में एक्सपोनेंट को शॉर्टकट का उपयोग करके कुशल गणना देने के लिए चुना जा सकता है, जो सामान्य गणित पुस्तकालयों को नहीं मान सकता है।

स्रोत

2012-06-30 07:59:24

बहुत बड़ी संख्या से निपटने के लिए, boost's Multiprecision लाइब्रेरी पर एक नज़र डालें। इसमें एक पाउम() फ़ंक्शन है जो इस उद्देश्य के लिए अच्छी तरह से काम करता है।

Generic Integer Operations से

template <class Integer> 
Integer powm(const Integer& b, const Integer& p, const Integer& m); 
रिटर्न ख ^पी% मीटर।

उदाहरण:

#include <boost/multiprecision/cpp_int.hpp> 

boost::multiprecision::cpp_int pow("8912627233012800753578052027888001981"); 
boost::multiprecision::cpp_int mod("0x86f71688cdd2612c117d1f54bdae029"); 
boost::multiprecision::cpp_int base(12345); 

boost::multiprecision::cpp_int result = powm(base, pow, mod); 

std::cout << "result is: " << result << std::endl;

प्रिंट:

result is: 5758534182572671080415167723795472693

स्रोत

2014-01-21 08:22:31 WawaBrother

मैं इस सुविधा का उपयोग इस समस्या को हल करने के लिए

यूवीए 374 - बिग मॉड

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=310

// a^b % T 

// with Exponentiation by squaring (http://en.wikipedia.org/wiki/Exponentiation_by_squaring#Basic_method) 

// if a very large use 
// R=(unsigned long long)(R*a)%T; 

int restOfPot(long long a,int b,int T) 
{ 
    a%=T; 
    long long R=1; 

    while(b) 
    { 
     if(b&1) R=(R*a)%T; 
     a=(a*a)%T; 
     b>>=1; 
    } 

    return int(R); 
}

स्रोत

2014-10-09 15:56:48

लेकिन, बी का मान डेटा प्रकार "सी लंबे समय" में फिट नहीं हो सकता है। उदाहरण के लिए बी 1000000000 वें फाइबोनैकी संख्या हो सकती है।

इस तरह बातें के लिए, उन्हें आसानी से ठीक है: याद

एक^(ब + स) == एक^b * एक^ग आधुनिक घ

आप कर सकते हैं Fibonacci संख्याओं की गणना करने के लिए उपयोग किए जाने वाले उसी प्रकार के रिकर्सन के बारे में आपके द्वारा पूछे जाने वाले विशेष उत्पाद की गणना करें - आपको बड़ी संख्या या मॉड्यूलर एक्सपोनेंटिएशन की आवश्यकता नहीं है!

एक और संस्करण है कि कभी कभी ऊपर आता है

एक^(ख * ग) = (क^ख)^ग आधुनिक घ

स्रोत

2015-05-09 09:48:51 Hurkyl

-1

#include <iostream> 
#include <math.h> 
#include <stdint.h> 

using namespace std; 

int main(){ 
int64_t a, b, k, d; 
cin >> a >> b >> k; 

int64_t poew = pow(a, b); 
d = poew % k; 

cout << d; 
}

क्योंकि int64_t पूर्णांक से भी बड़ा रेंज है है

स्रोत

2015-05-09 11:02:56

सवाल यह कहता है कि 'बी' का मूल्य बहुत बड़ा हो सकता है और इसलिए पाउ (ए, बी) 64 बिट लंबी डेटा संरचना में भी लड़ नहीं सकता है। –

गणना (ए^बी)% एमओडी

उत्तर

संबंधित मुद्दे